1719 測資加強 已 rejudge
2049 . 龜兔賽跑
Description
在龜兔國裡面，有一座森林，在這個森林之中有 $ n $ 座城市，之間以 $ m $ 條雙向的道路連接。
小龜和小兔想要比賽跑步，但是因為他們實力差距太大，所以造成比賽不公平。
所以他們決定小兔必須禮讓小龜，小龜至多可以選一座城市 $ x $ ，並且規定在比賽的過程中，小兔不能經過這座城市。
不過為了使比賽能夠進行，小龜不能選擇小兔一定要經過的城市，不然就不用比了...
比賽從城市 $ S $ 開始，$ T $ 結束
為了最快跑到終點，小龜和小兔都會選擇盡可能短的路徑跑到終點，當然 這兩段路徑的長度差距，全部都掌握在小龜的手中。
聰明的你 可以告訴小龜，選擇哪一座城市可以使得小兔多跑最多嘛？
Input Format
第一行有 4 個正整數 $ n, m (3 \leq n \leq 3 \times 10^ 5 , n-1 \leq m \leq 3 \times 10^ 5 ), S, T (1 \leq S, T \leq n) $
保證 $ S \neq T $
接下來 m 行 各有 3 個正整數 $ a, b(1 \leq a, b \leq n), w(0 \leq w \leq 10^ 9 )$
代表有一條連接城市 $a, b$ 的道路 其長度為 $w$
保證存在從 $ S $ 到 $ T $ 的路徑
Output Format
請輸出一個正整數代表小龜最好的 $ x $ 以及在規定下，小兔要完成比賽最少要跑多遠（數字間以空白隔開
如果有多組答案 請輸出編號最小的
如果在條件之下，小龜沒有任何選擇，那請輸出 -1
Sample Input 1
9 10 1 5
1 2 2
2 3 4
2 6 3
2 7 5
3 4 8
6 8 9
4 8 20
7 9 10
4 9 100
4 5 16
1 2 2
2 3 4
2 6 3
2 7 5
3 4 8
6 8 9
4 8 20
7 9 10
4 9 100
4 5 16
Sample Output 1
3 50
Sample Input 2
7 9 1 5
1 2 10
2 7 20
2 3 10
3 7 2
3 6 5
6 7 3
3 4 10
4 6 16
4 5 10
1 2 10
2 7 20
2 3 10
3 7 2
3 6 5
6 7 3
3 4 10
4 6 16
4 5 10
Sample Output 2
3 59
Sample Input 3
2 2 1 2
1 2 10
2 2 0
1 2 10
2 2 0
Sample Output 3
-1 10
Hints
題目並沒有保證最短路徑會唯一喔！
題解
Problem Source
如果測資有問題
請通知我
by kevin_zhang
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~21 | $n, m \leq 1000 $ | 25 |
| 2 | 0~63 | no additional limits | 75 |