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. template<typename T>
  12. bool minimize(T& a, const T& b) {
  13. 	if (b < a) {a = b; return true;}
  14. 	return false;
  15. }
  16.  
  17. const int N = 1e5 + 5;  
  18.  
  19. int n, m; 
  20. int s, t, a, b;  
  21. vector<ii> adj[N]; 
  22.  
  23. struct Node {
  24. 	int u; ll d; 
  25. 	bool operator<(const Node& other) const {
  26. 		return d > other.d; 
  27. 	}
  28. };
  29.  
  30. ll dist_s[N]; 
  31. ll dist_t[N]; 
  32. ll dist_a[N]; 
  33. ll dist_b[N]; 
  34.  
  35. void dijkstra(int s, ll dist[]) {
  36. 	for (int u = 1; u <= n; u++) dist[u] = LINF;  
  37.  
  38. 	priority_queue<Node> pq; 
  39. 	dist[s] = 0;  
  40. 	pq.push({s, dist[s]});  
  41.  
  42. 	while (!pq.empty()) {
  43. 		Node front = pq.top(); pq.pop(); 
  44. 		int u = front.u; ll d = front.d;  
  45.  
  46. 		if (d > dist[u]) continue; 
  47.  
  48. 		for (ii v : adj[u]) {
  49. 			if (minimize(dist[v.first], dist[u] + v.second)) {
  50. 				pq.push({v.first, dist[v.first]}); 
  51. 			}
  52. 		}
  53. 	}
  54. }
  55.  
  56. // Đáp án sẽ có dạng a ->  x  ->  y  ->  b hoặc b  ->  x  ->  y  -> a
  57. // hay 				 dist_a[x] + dist_b[y] hoặc dist_b[x] + dist_a[y]
  58. // Với đường đi x -> y thuộc vào một đường đi ngắn nhất nào đấy đi từ s đến t 
  59. // hay x -> y là một đường đi trên đồ thị đường đi ngắn nhất của s, t
  60.  
  61. vector<int> g[N]; 
  62.  
  63. ll memo[N];  
  64.  
  65. // dp_a(x) = min({dist_a(y)}) với mọi y sao cho tồn tại đường đi x -> y trên đồ thị đường đi ngắn nhất 
  66. ll dp_a(int x) {
  67. 	ll& ans = memo[x];  
  68. 	if (ans != -1) return ans; 
  69. 	ans = dist_a[x];  
  70. 	for (int nxt_x : g[x]) {
  71. 		minimize(ans, dp_a(nxt_x)); 
  72. 	}
  73. 	return ans; 
  74. }
  75.  
  76. // dp_b(x) = min({dist_b(y)}) với mọi y sao cho tồn tại đường đi x -> y trên đồ thị đường đi ngắn nhất
  77. ll dp_b(int x) {
  78. 	ll& ans = memo[x];  
  79. 	if (ans != -1) return ans; 
  80. 	ans = dist_b[x]; 
  81. 	for (int nxt_x : g[x]) {
  82. 		minimize(ans, dp_b(nxt_x)); 
  83. 	}
  84. 	return ans; 
  85. }
  86.  
  87. int main() {
  88. 	ios::sync_with_stdio(false); 
  89. 	cin.tie(nullptr); 	
  90. 	cin >> n >> m; 
  91. 	cin >> s >> t; 
  92. 	cin >> a >> b;   
  93.  
  94. 	for (int i = 0; i < m; i++) {
  95. 		int u, v, w; 
  96. 		cin >> u >> v >> w; 
  97. 		adj[u].push_back({v, w}); 
  98. 		adj[v].push_back({u, w}); 
  99. 	}
  100.  
  101. 	// Build đồ thị đường đi ngắn nhất với đỉnh xuất phát s, đỉnh kết thúc t
  102. 	dijkstra(s, dist_s); 
  103. 	dijkstra(t, dist_t); 
  104.  
  105. 	for (int u = 1; u <= n; u++) {
  106. 		for (ii v : adj[u]) {
  107. 			if (dist_s[u] + v.second + dist_t[v.first] == dist_s[t]) {
  108. 				g[u].push_back(v.first); 
  109. 			}
  110. 		}
  111. 	}
  112.  
  113. 	dijkstra(a, dist_a); 
  114. 	dijkstra(b, dist_b); 
  115.  
  116. 	// Trường hợp a -> x -> y -> b
  117. 	memset(memo, -1, sizeof memo);  
  118. 	ll ans = dist_a[b]; 
  119. 	for (int x = 1; x <= n; x++) {
  120. 		minimize(ans, dist_a[x] + dp_b(x)); 
  121. 	}
  122.  
  123. 	// Trường hợp b -> x -> y -> a
  124. 	memset(memo, -1, sizeof memo);  
  125. 	for (int x = 1; x <= n; x++) {
  126. 		minimize(ans, dist_b[x] + dp_a(x)); 
  127. 	}
  128.  
  129. 	cout << ans << '\n'; 
  130. }
Success #stdin #stdout 0.01s 12224KB
comments (?)
stdin
copy 
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
stdout
copy 
2
https://ideone.com/5ubm9e
language:
C++14 (gcc 8.3)
created:
281 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!