ASC 22C Important Roads：最短路 + 雙連通分量/拓撲排序找關鍵邊

問題描述

無向圖 n≤20,000 點，m≤100,000 邊，起點 1，終點 n。找出所有「重要道路」：刪除後從 1 到 n 的最短路長度增加（或不可達）。

解題思路

1. 從起點 1 跑 Dijkstra + 堆優化，得到 dist[u] = 1 到 u 的最短距離
2. 構建最短路圖：保留滿足 dist[u] + w(u,v) = dist[v] 的有向邊 u→v
3. 在最短路圖中找關鍵邊，有兩種等效方法：

方法一：無向圖雙連通分量找橋

將最短路圖視為無向圖，橋（割邊）即為重要道路。因為刪除橋會斷開連通性，導致無法從 1 到 n 或最短路變長。

方法二：有向圖拓撲排序（隊友神解法）

最短路圖是 DAG（有向無環圖）。按拓撲序遍歷，維護全局變量 diff = 當前點的出度 - 入度（在已遍歷子圖中）。若某點的 diff == 1，則其出邊為關鍵邊。原理：該邊是連接前半部分和後半部分的唯一通道。

核心代碼框架

// 1. Dijkstra 求最短路
// 2. 建立最短路 DAG
// 3. 方法一：Tarjan 找橋
// 4. 方法二：拓撲序 + diff 計數
// 5. 輸出重要邊的原始索引

關鍵點總結

• SPFA 不穩定，必須用 Dijkstra + 堆
• 最短路圖構建：僅保留最短路上的邊，且方向從起點指向終點
• 橋的定義：無向圖中刪除後連通分量增加的邊
• 拓撲法更簡潔，只需一次遍歷，無需構建無向圖