fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #include<algorithm>
  5. using namespace std;
  6.  
  7. int N, E;
  8. vector<vector<pair<int, int>>> adj;
  9.  
  10. int dijkstra(int start, int end) {
  11. 	priority_queue<pair<int, int>> pq; // -거리, 정점
  12. 	vector<int> dist(N + 1, 987654321);
  13. 	pq.push({0, start});
  14. 	dist[start] = 0;
  15. 	while(!pq.empty()) {
  16. 		int dst = -pq.top().first;
  17. 		int vertex = pq.top().second;
  18. 		pq.pop();
  19. 		if(vertex == end)
  20. 			break;
  21. 		if(dist[vertex] < dst)
  22. 			continue;
  23. 		for(auto& iter : adj[vertex]) {
  24. 			int nextDst = iter.second + dst;
  25. 			int nextVertex = iter.first;
  26. 			if(dist[nextVertex] > nextDst) {
  27. 				dist[nextVertex] = nextDst;
  28. 				pq.push({-nextDst, nextVertex});
  29. 			}
  30. 		}
  31. 	}
  32. 	return dist[end];
  33. }
  34.  
  35. int main() {
  36. 	ios::sync_with_stdio(false);
  37. 	cin.tie(0);
  38. 	cin >> N >> E;
  39. 	adj.resize(N + 1);
  40. 	for(int i = 0; i != E; ++i) {
  41. 		int a, b, c;
  42. 		cin >> a >> b>> c;
  43. 		adj[a].push_back({b, c});
  44. 		adj[b].push_back({a, c});
  45. 	}
  46. 	int viaPointA, viaPointB;
  47. 	cin >> viaPointA >> viaPointB;
  48. 	long long retA = (long long)dijkstra(1, viaPointA) + dijkstra(viaPointA, viaPointB) + dijkstra(viaPointB, N);
  49. 	long long retB = (long long)dijkstra(1, viaPointB) + dijkstra(viaPointB, viaPointA) + dijkstra(viaPointA, N);
  50. 	if(retA > 987654321 && retB > 987654321)
  51. 		cout << -1;
  52. 	else
  53. 		cout << min(retA, retB);
  54. }
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
2 0
1 2
stdout
copy 
987654321
https://ideone.com/6C5Lwm
language:
C++14 (gcc 8.3)
created:
4 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!