40009. Practice 9: 死對頭問題

I'm a slow walker, but I never walk backwards.

從前從前,在「單行道國」中有兩個人,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/Output

第一行有一個正整數$T$,代表總共有多少筆測資。 對於每筆測資,第一行有兩個正整數$N,M$,代表單行道國有$N$個小鎮和$M$條單行道;第二行有兩個非負整數$A,B$,分別代表John住的小鎮編號與他要去的小鎮編號。 接下來有$M$行,每一行有三個非負整數$A_i, B_i, K_i$,代表有一條小鎮$A_i$到小鎮$B_i$的單行道,且走這條路要繳$K_i$元的過路費。

對於每筆測資輸出一行包含一個整數,代表John繳的總過路費減掉Jon繳的總過路費

Subtasks/Constraints

所有測資皆符合: $T\leq 20; 2\leq N,M\leq 10^ 5;1\leq K_i\leq 10^ 9$

  1. $K_i=1$ (20 pts)
  2. 如果不重複經過小鎮,則從一小鎮到另一小鎮將只有唯一的路線可以通行 (30 pts)
  3. $N,M\leq 500$ (10 pts)
  4. $N,M\leq 5000$ (10 pts)
  5. 無額外限制 (40 pts)

Sample Input

1
3 6
0 1
0 1 2
1 0 3
0 2 7
2 1 6
2 1 7
1 2 8

Sample Output

5

範例測資中,Jon會走0->1,總共花2元;John會走0->1->0->1,總共花7元。(0->2->1要花13元,並不是最佳的走法。)

Discussion