fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12. const int MOD = 1e9 + 9277; 
  13.  
  14. void add(int& a, int b) {
  15. 	a += b; 
  16. 	if (a >= MOD) a -= MOD; 
  17. }
  18.  
  19. struct Edge {
  20. 	int u, v, w; 
  21. }; 
  22.  
  23. int n, m, s, t; 
  24. vector<ii> adj[N], radj[N]; 
  25. vector<Edge> edges;  
  26.  
  27. struct Node {
  28. 	int u; ll d; 
  29. 	bool operator<(const Node& other) const {
  30. 		return d > other.d; 
  31. 	}
  32. }; 
  33.  
  34. ll dist_s[N]; // dist_s[u] = Đường đi ngắn nhất từ s đến u
  35. ll dist_t[N]; // dist_t[u] = Đường đi ngắn nhất từ u đến t
  36. int cnt_s[N]; // cnt_s[u] = Số đường đi ngắn nhất từ s đến u
  37. int cnt_t[N]; // cnt_t[u] = Số đường đi ngắn nhất từ u đến t
  38.  
  39. void dijkstra(int s, vector<ii> adj[], ll dist[], int cnt[]) {
  40. 	for (int u = 1; u <= n; u++) {
  41. 		dist[u] = LINF;  
  42. 		cnt[u] = 0; 
  43. 	}
  44.  
  45. 	priority_queue<Node> pq; 
  46. 	dist[s] = 0; 
  47. 	cnt[s] = 1; 
  48. 	pq.push({s, dist[s]}); 
  49.  
  50. 	while (!pq.empty()) {
  51. 		Node front = pq.top(); pq.pop();  
  52. 		int u = front.u; ll d = front.d;  
  53.  
  54. 		if (d > dist[u]) continue; 
  55.  
  56. 		for (ii v : adj[u]) {
  57. 			if (dist[u] + v.second < dist[v.first]) {
  58. 				dist[v.first] = dist[u] + v.second; 
  59. 				cnt[v.first] = cnt[u]; 
  60. 				pq.push({v.first, dist[v.first]}); 
  61. 			}
  62. 			else if (dist[u] + v.second == dist[v.first]) {
  63. 				add(cnt[v.first], cnt[u]); 
  64. 			}
  65. 		}
  66. 	}
  67. }
  68.  
  69. int main() {
  70. 	ios::sync_with_stdio(false); 
  71. 	cin.tie(nullptr); 	
  72. 	cin >> n >> m >> s >> t; 
  73.  
  74. 	for (int i = 0; i < m; i++) {
  75. 		int u, v, w; 
  76. 		cin >> u >> v >> w; 
  77. 		adj[u].push_back({v, w}); 
  78. 		radj[v].push_back({u, w}); 
  79. 		edges.push_back({u, v, w}); 
  80. 	}
  81.  
  82. 	dijkstra(s, adj, dist_s, cnt_s);
  83. 	dijkstra(t, radj, dist_t, cnt_t);  
  84.  
  85. 	for (Edge e : edges) {
  86. 		if (dist_s[e.u] == LINF || dist_t[e.v] == LINF) {
  87. 			cout << "NO" << '\n'; 
  88. 			continue; 
  89. 		}
  90.  
  91. 		// Điều kiện để cạnh e nằm trên MỌI đường đi ngắn nhất từ s đến t
  92. 		if (dist_s[e.u] + e.w + dist_t[e.v] == dist_s[t] && 1ll * cnt_s[e.u] * cnt_t[e.v] % MOD == cnt_s[t]) {
  93. 			cout << "YES" << '\n'; 
  94. 		}
  95. 		else {
  96. 			// Trọng số new_w để e nằm trên MỌI đường đi ngắn nhất từ s đến t
  97. 			int new_w = dist_s[t] - dist_s[e.u] - dist_t[e.v] - 1;  
  98. 			int cost = e.w - new_w;   
  99.  
  100. 			if (new_w > 0) {
  101. 				cout << "CAN " << cost << '\n'; 
  102. 			}
  103. 			else {
  104. 				cout << "NO" << '\n'; 
  105. 			}
  106. 		}
  107. 	}
  108. }
Success #stdin #stdout 0.01s 9556KB
comments (?)
stdin
copy 
6 7 1 6
1 2 2
1 3 10
2 3 7
2 4 8
3 5 3
4 5 2
5 6 1
stdout
copy 
YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES
https://ideone.com/R2c1c9
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!