fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <numeric>
  6. using namespace std;
  7.  
  8. typedef pair<int,int> pii;
  9. typedef long long ll;
  10.  
  11. const ll inf = (ll)1e18+7;
  12.  
  13. template<typename T> bool setmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
  14. template<typename T> bool setmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
  15.  
  16.  
  17. int main()
  18. {
  19. 	int n, m;
  20. 	cin >> n >> m;
  21. 	int s, t;
  22. 	cin >> s >> t;
  23. 	s--; t--;
  24. 	int u, v;
  25. 	cin >> u >> v;
  26. 	u--; v--;
  27.  
  28. 	vector<vector<pii> > adj(n);
  29. 	for (int i = 0; i < m; i++) {
  30. 		int a, b, c;
  31. 		cin >> a >> b >> c;
  32. 		a--; b--;
  33. 		adj[a].push_back({b, c});
  34. 		adj[b].push_back({a, c});
  35. 	}
  36. 	auto dijkstra = [&](vector<vector<pii> >& g, int a) {
  37. 		typedef pair<ll,int> point;
  38. 		vector<ll> dist(n, inf);
  39. 		priority_queue<point, vector<point>, greater<point> > pq;
  40. 		dist[a] = 0;
  41. 		pq.push({0ll, a});
  42. 		while (not pq.empty()) {
  43. 			auto [d, cur] = pq.top(); pq.pop();
  44. 			if (d != dist[cur]) continue;
  45. 			for (auto [nxt, w] : g[cur]) {
  46. 				if (setmin(dist[nxt], d + w)) {
  47. 					pq.push({dist[nxt], nxt});
  48. 				}
  49. 			}
  50. 		}
  51. 		return dist;
  52. 	};
  53. 	auto distS = dijkstra(adj, s);
  54. 	auto distT = dijkstra(adj, t);
  55. 	auto distU = dijkstra(adj, u);
  56. 	auto distV = dijkstra(adj, v);
  57. 	auto sortedOrder = [&](const vector<ll>& v) {
  58. 		vector<int> order(v.size());
  59. 		iota(order.begin(), order.end(), 0);
  60. 		sort(order.begin(), order.end(), [&](int a, int b) { return v[a] < v[b]; });
  61. 		return order;
  62. 	};
  63. 	ll totDist = distS[t];
  64. 	ll ans = inf;
  65. 	{
  66. 		auto ordS = sortedOrder(distS);
  67. 		auto dp = distU;
  68. 		for (int a : ordS) {
  69. 			for (auto&& [b, w] : adj[a]) {
  70. 				if (distS[a] + w + distT[b] == totDist) {
  71. 					setmin(dp[b], dp[a]);
  72. 				}
  73. 			}
  74. 		}
  75. 		for (int i = 0; i < n; i++) {
  76. 			setmin(ans, distV[i] + dp[i]);
  77. 		}
  78. 	}
  79. 	{
  80. 		auto ordT = sortedOrder(distT);
  81. 		auto dp = distU;
  82. 		for (int a : ordT) {
  83. 			for (auto&& [b, w] : adj[a]) {
  84. 				if (distT[a] + w + distS[b] == totDist) {
  85. 					setmin(dp[b], dp[a]);
  86. 				}
  87. 			}
  88. 		}
  89. 		for (int i = 0; i < n; i++) {
  90. 			setmin(ans, distV[i] + dp[i]);
  91. 		}
  92. 	}
  93. 	cout << ans << endl;
  94. }
Success #stdin #stdout 0s 4916KB
comments (?)
stdin
copy 
10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
stdout
copy 
19
https://ideone.com/tCpCIA
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!