fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using P = pair<ll,ll>;
  5. int main() {
  6. 	int n,m;
  7. 	cin>>n>>m;
  8.  
  9. 		ll a, b , c;
  10. 	cin>>a>>b>>c;
  11. 	vector<vector<pair<ll,ll>>>G(n+1);
  12. 	for(int i = 0 ;i < m ;i++){
  13. 		ll u,v,w;
  14. 		cin>>u>>v>>w;
  15. 		G[u].push_back({v,w});
  16. 		G[v].push_back({u,w});
  17.  
  18. 	}
  19.  
  20.  
  21.  
  22.  
  23. 		ll ans = 1e18;
  24. 	for(int src = 0 ; src<=n ;src++){
  25. 			priority_queue<P,vector<P>,greater<P>>pq;
  26. 	vector<ll>dist(n+1,1e18);
  27. 	dist[src]=0;
  28. 	pq.push({0,src});
  29.  
  30. 	while(!pq.empty()){
  31. 		ll d,node;
  32. 		tie(d,node)=pq.top();
  33. 		pq.pop();
  34.  
  35. 		if(dist[node]>d)continue;
  36.  
  37. 		for(auto u : G[node]){
  38. 			ll neigh = u.first;
  39. 			ll w = u.second;
  40.  
  41. 			if(dist[neigh]>dist[node]+w){
  42. 				dist[neigh]=dist[node]+w;
  43. 				pq.push({dist[neigh],neigh});
  44. 			}
  45. 		}
  46. 	}
  47.  
  48. 	if(dist[a]<1e18 && dist[b]<1e18 && dist[c]<1e18 ){
  49. 		ans = min(ans,dist[a]+dist[b]+dist[c]);
  50. 	}
  51. 	}
  52. 	if(ans == 1e18)cout<<-1;
  53. 	else cout<<ans;
  54. 	return 0;
  55. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
3 3 
0 2 1 
0 2 4
0 1 10
1 2 5
stdout
copy 
9
https://ideone.com/BrFVzv
language:
C++ (gcc 8.3)
created:
13 hours 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!