CSES 1203 Visiting Cities

題目概述

求出給你一張有向帶權圖，保證一定有一條路能夠從 11 走到 nn ，請你求出 11 到 nn 最短路上必經的點。

題解

對於那些必經的點 pp ，一定滿足 dis(1,p)=dis(p,n)dis(1, p) = dis(p, n) ，其中 dis(u,v)dis(u, v) 為 u→vu \to v 的最短路徑長度。
還有滿足 ways(1,p)⋅ways(p,n)=ways(1,n)ways(1, p) \cdot ways(p, n) = ways(1, n)，其中 ways(u,v)ways(u, v) 為 u→vu \to v的路徑數，由於路徑數量會很多，所以可以選一個數字取模，但因為有進行取模的動作，所以不保證答案一定正確。
而每次檢查就是把 11 和 nn 各做為起點去跑 dijkstra ，然後看有沒有符合條件，多產生幾組模數多檢查幾次降低錯誤率就好。

AC Code

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
64
65
66
#include<bits/stdc++.h>
#define pii pair<long long, int>
#define pb push_back
using namespace std;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<long long> distrib((long long) 1e9, (long long) 2e9);
void solve(){
	int n, m;
	cin>>n>>m;
	vector<vector<pair<int,int>>>g(n+1);
	vector<vector<pair<int,int>>>rg(n+1);
	for(int i = 0;i < m;++i){
		int u, v, w;
		cin>>u>>v>>w;
		g[u].push_back({v, w});
		rg[v].push_back({u, w});
	}
	auto dijkstra = [&](vector<long long> &dis, vector<long long> &ways, int st, long long mod,const vector<vector<pair<int,int>>> &g){
		priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
		dis[st] = 0, ways[st] = 1;
		pq.push({dis[st], st});
		while(!pq.empty()){
			auto [now, u] = pq.top();
			pq.pop();
			if(now>dis[u])continue;
			for(auto [v, w] : g[u]){
				if(dis[v] > dis[u] + w){
					ways[v] = ways[u];
					dis[v] = dis[u] + w;
					pq.push({dis[v], v});
				}
				else if(dis[v] == dis[u] + w){
					ways[v] += ways[u];
					ways[v] %= mod;
				}
			}
		}
	};
	vector<int>ans(n+5, 0);
	auto check = [&](vector<int> &ans){
		vector<vector<long long>>dis(2, vector<long long>(n+1, 2e18)), ways(2, vector<long long>(n + 1));
		long long mod = distrib(mt);
		dijkstra(dis[0], ways[0], 1, mod, g);
		dijkstra(dis[1], ways[1], n, mod, rg);
		vector<int> tmp;
		for(int i = 1;i <= n;++i){
			if(dis[0][i] + dis[1][i] == dis[0][n] && ways[0][i] * ways[1][i] % mod == ways[0][n]){
				tmp.push_back(i);
			}
		}
		if(tmp.size() < ans.size()){
			ans = tmp;
		}
	};
	for(int i = 0;i < 5;++i)check(ans);
	cout<<ans.size()<<endl;
	for(auto i:ans)cout<<i<<' ';
	cout<<endl;
 
 
}
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t = 1;
	while(t--)solve();
}