無向加權圖的最短距離

題目敘述

某校園裡有 n 個地點，編號 1 到 n，其間有 m 條雙向小路，每條小路有一個通行時間。給定出發地點 s 與目的地點 t，請算出從 s 走到 t 所需的最短總時間。所有通行時間都不是負數，所以這是標準的單源最短路徑問題。若 t 無法從 s 走到，輸出 −1。

同一對地點之間可能有多條小路，此時應採用其中通行時間最小的那一條。

輸入格式

• 第 1 行：整數 n 與 m，表示地點數與小路數。
• 接下來 m 行：每行三個整數 u、v、w，表示 u 與 v 之間有一條雙向小路，通行時間為 w。
• 最後一行：整數 s 與 t，表示出發點與目的地。

輸出格式

輸出最短總時間（以有符號 64 位元整數表示）。若無法從 s 抵達 t，輸出 −1。

限制

• 1 ≤ n ≤ 50000
• 0 ≤ m ≤ O(n)（測試包含鏈狀與稠密情況）
• 1 ≤ w ≤ 10⁹
• 圖為無向圖，同一對頂點間可能有平行邊，取權重最小者。

範例

範例 1

輸入

4 3
1 2 1
2 4 1
1 4 5
1 4

輸出

2

直接走 1−4 要 5，但 1 → 2 → 4 只要 1 + 1 = 2，所以答案是 2。

範例 2

輸入

1 0
1 1

輸出

0

起點與終點相同時，距離為 0，即使完全沒有邊。

範例 3

輸入

3 1
1 2 3
1 3

輸出

-1

地點 3 沒有任何小路相連，從 1 無法抵達。

範例 4

輸入

2 2
1 2 5
1 2 2
1 2

輸出

2

1 與 2 之間有權重 5 與 2 兩條平行邊，應取較小的 2；若只用先讀到的那條會得到 5。

範例 5

輸入

4 3
1 2 1
2 3 2
1 4 5
4
1 4

輸出

5

s = 4、t = 1。只有一條路 4 − 1，耗時 5。讀完 m 條邊後，只有緊接著的兩個整數是 s 與 t，之後多餘的數字不使用。

範例 6

輸入

3 2
1 2 5
2 3 1
3
1 3

輸出

6

s = 3、t = 1，路徑 3 → 2 → 1 耗時 1 + 5 = 6。同樣只讀邊之後的前兩個整數作為 s、t。

說明

• 距離請用 64 位元整數儲存；O(n²) 的做法在大測資會逾時，建議使用優先佇列。
• 本題權重皆為正，不會出現負邊。
• 同一對頂點若讀到多條邊，只保留權重最小者，不是最後一條，也不是總和。
• 以優先佇列實作時，同一頂點可能留有多筆過期的較大距離，彈出後若該頂點已確定就略過。