TIOJ-2058

發表於 更新於 Disqus：

從前從前，在「單行道國」中有兩個人，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繳的總過路費差了多少錢嗎？

$T\le 20, N, M\le 10^5, K_i\le 10^9$。

其實就是嚴格次短路徑辣.jpg。那要怎麼做呢?
只要不斷更新最短路徑的同時，把舊的最短路徑丟給次短路徑就好(或者只能更新次短路徑就更新)，就一般的dijkstra可解。
記得pq中最短和次短都要丟，這樣才能好好更新(我也不太知道原因，反正就是這樣(誤))。
複雜度$\mathcal{O}(ElogE)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	EmiliaMyWife

	int t;
	cin >> t;
	while(t--) {
		int s, t, n, m;
		cin >> n >> m >> s >> t;
		vector<ll> dis(n, LINF), dis2(n, LINF);
		vector<vector<pair<int, int>>> edge(n);
		for(int i = 0, a, b, c; i < m; i++)
			cin >> a >> b >> c, edge[a].push_back({b, c});
		dis[s] = 0;
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
		pq.push({0, s});
		while(!pq.empty()) {
			auto [d, v] = pq.top();
			pq.pop();
			if(dis2[v] < d)
				continue;
			for(auto [u, c] : edge[v]) {
				ll xx = d + c;
				if(xx < dis[u]) {
					swap(dis[u], xx);
					pq.push({dis[u], u});
				}
				if(xx < dis2[u] && xx != dis[u]) {
					dis2[u] = xx;
					pq.push({dis2[u], u});
				}
			}
		}
		cout << dis2[t] - dis[t] << '\n';
	}

	return 0;
}