fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. #define int long long 
  4.  
  5. using namespace std;  
  6.  
  7. typedef long long ll;  
  8. typedef pair<int, int> ii;  
  9.  
  10. const int INF = 1e9;  
  11. const ll LINF = 1e18;  
  12.  
  13. const int N = 1e5 + 5; 
  14. const int MOD = 1e9 + 9277; // nên chọn MOD lạ một chút, những MOD như 1e9 + 7, 1e9 + 9 quá phổ biến
  15.  
  16. void add(int& a, int b) {
  17. 	a += b; 
  18. 	if (a >= MOD) a -= MOD; 
  19. }
  20.  
  21. int n, m;  
  22. vector<ii> adj[N], radj[N]; 
  23.  
  24. struct Node {
  25. 	int u; ll d;  
  26. 	bool operator<(const Node& other) const {
  27. 		return d > other.d; 
  28. 	}
  29. }; 
  30.  
  31. ll dist_1[N]; // dist_1[u] = Đường đi ngắn nhất từ 1 đến u 
  32. ll dist_n[N]; // dist_n[u] = Đường đi ngắn nhất u đến n
  33. int cnt_1[N]; // cnt_1[u] = Số đường đi ngắn nhất từ 1 đến u 
  34. int cnt_n[N]; // cnt_n[u] = Số đường đi ngắn nhất từ u đến n
  35.  
  36. void dijkstra(int s, vector<ii> adj[], ll dist[], int cnt[]) {
  37. 	for (int u = 1; u <= n; u++) {
  38. 		dist[u] = LINF; 
  39. 		cnt[u] = 0;  
  40. 	}
  41.  
  42. 	priority_queue<Node> pq;  
  43. 	dist[s] = 0;  
  44. 	cnt[s] = 1;   
  45. 	pq.push({s, dist[s]});  
  46.  
  47. 	while (!pq.empty()) {
  48. 		Node front = pq.top(); pq.pop();  
  49. 		int u = front.u; ll d = front.d;  
  50.  
  51. 		if (d > dist[u]) continue;  
  52.  
  53. 		for (ii v : adj[u]) {
  54. 			if (dist[u] + v.second < dist[v.first]) {
  55. 				dist[v.first] = dist[u] + v.second;  
  56. 				cnt[v.first] = cnt[u];                             
  57. 				pq.push({v.first, dist[v.first]});  
  58. 			}
  59. 			else if (dist[u] + v.second == dist[v.first]) {
  60. 				add(cnt[v.first], cnt[u]);  
  61. 			}
  62. 		}
  63. 	}
  64. }
  65.  
  66. signed main() {
  67. 	ios::sync_with_stdio(false); 
  68. 	cin.tie(nullptr); 	
  69. 	cin >> n >> m; 
  70.  
  71. 	for (int i = 0; i < m; i++) {
  72. 		int u, v, w; 
  73. 		cin >> u >> v >> w; 
  74. 		adj[u].push_back({v, w}); 
  75. 		radj[v].push_back({u, w}); 
  76. 	}
  77.  
  78. 	dijkstra(1, adj, dist_1, cnt_1); 
  79. 	dijkstra(n, radj, dist_n, cnt_n); 
  80.  
  81. 	vector<int> ans;  
  82. 	for (int u = 1; u <= n; u++) {
  83. 		// Điều kiện để đỉnh u nằm trên MỌI đường đi ngắn nhất từ 1 đến n
  84. 		if (dist_1[u] + dist_n[u] == dist_1[n] && 1ll * cnt_1[u] * cnt_n[u] % MOD == cnt_1[n]) {
  85. 			ans.push_back(u); 
  86. 		}
  87. 	}
  88.  
  89. 	cout << ans.size() << '\n'; 
  90. 	for (int u : ans) cout << u << ' '; 
  91. }
Success #stdin #stdout 0.01s 9476KB
comments (?)
stdin
copy 
5 6
1 2 3
1 3 4
2 3 1
2 4 5
3 4 1
4 5 8
stdout
copy 
4
1 3 4 5
https://ideone.com/oJFHVH
language:
C++14 (gcc 8.3)
created:
282 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!