2058 . 死對頭問題
TopCoder
Tags
Description
從前從前，在「單行道國」中有兩個人，John和Jon。他們兩個人是死對頭，而且都住在同一個小鎮$A$。
「單行道國」顧名思義，這個國家每一條路都是連接兩個小鎮的單行道，並且國家中總共有$N$個小鎮，從$0$編號到$N-1$。這個國家的交通其實相當發達，所以對於任意兩個小鎮$X,Y$，都存在路線可以從$X$走到$Y$。另外，有些小鎮之間可能會兩個方向的單行道各有一條；甚至在重要的小鎮之間可能會有很多條起終點一樣的單行道。當然，單行道國的政府也看上了他們國家交通發達這件事情，於是決定在每一條道路都蓋一個收費站，任何一個開車經過的人民都要收過路費。
某一天，John要到$B$鎮去旅遊。沒想到，在他收拾好一切行李準備出發的時候，他卻聽說兩天前Jon剛好也去了$B$鎮一趟！身為Jon的死對頭，John決定說什麼也不要和Jon走類似的路線。幸好John知道Jon是個非常節省的人，所以Jon從$A$鎮到$B$鎮時一定會挑選總過路費最少的路線前往。
因此，John算出了Jon從$A$鎮到$B$鎮時繳了多少過路費，並且決定自己從$A$鎮前往$B$鎮的時候繳的總過路費一定要跟Jon不一樣。在滿足這個前提之下，John會讓自己繳的總過路費愈少愈好（當然，這樣有可能是必須要繞路的，也就是說John走的路線可能會重複經過某個小鎮或重複經過某一條單行道）。你能幫John算出他繳的總過路費和Jon繳的總過路費差了多少錢嗎？
Input Format
第一行有一個正整數$T$，代表總共有多少筆測資。
對於每筆測資，第一行有兩個正整數$N,M$，代表單行道國有$N$個小鎮和$M$條單行道；第二行有兩個非負整數$A,B$，分別代表John住的小鎮編號與他要去的小鎮編號。
接下來有$M$行，每一行有三個非負整數$A_i, B_i, K_i$，代表有一條小鎮$A_i$到小鎮$B_i$的單行道，且走這條路要繳$K_i$元的過路費。
對於所有測資，$1\leq T\leq 20; 2\leq N,M\leq 10^ 5;1\leq K_i\leq 10^ 9$。
Output Format
對於每筆測資輸出一行包含一個整數，代表John繳的總過路費減掉Jon繳的總過路費。
Sample Input 1
3 4
0 1
0 1 2
1 0 3
0 2 7
2 1 6
Sample Output 1
Hints
範例測資中，Jon會走0->1，總共花2元；John會走0->1->0->1，總共花7元。（0->2->1要花13元，並不是最佳的走法。）
Problem Source
Problem Set by Yihda Yol
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 每一條單行道的過路費都是1 | 20 |
| 2 | 1 | 如果不重複經過小鎮，則從一小鎮到另一小鎮將只有唯一的路線可以通行 | 20 |
| 3 | 2 | $N,M \leq 500$ | 10 |
| 4 | 2~3 | $N,M \leq 5000$ | 10 |
| 5 | 0~4 | 無額外限制 | 40 |