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. 	ll n,m;
  7. 	cin>>n>>m;
  8. 	vector<vector<P>>G(n+1);
  9. 	for(int i = 0;i<m;i++){
  10. 		ll u,v,w;
  11. 		cin>>u>>v>>w;
  12. 		G[u].push_back({v,w});
  13. 		G[v].push_back({u,w});
  14. 	}
  15.  
  16. 	ll src;
  17. 	cin>>src;
  18. 	priority_queue<P,vector<P>,greater<P>>pq;
  19. 	vector<ll>dist(n+1,1e18);
  20. 	pq.push({0,src});
  21. 	dist[src]=0;
  22.  
  23. 	while(!pq.empty()){
  24. 		auto u = pq.top();
  25. 	     ll x = u.first;
  26. 	     ll y = u.second;
  27. 	     pq.pop();
  28. 	    if(x > dist[y]) continue;
  29. 	     for(auto v : G[y]){
  30. 	     	ll x1 = v.first;
  31. 	     	ll y1 = v.second;
  32.  
  33. 	     	if(dist[x1] > dist[y]+y1){
  34. 	     		dist[x1] = dist[y]+y1;
  35. 	     		pq.push({dist[x1],x1});
  36. 	     	}
  37. 	     }
  38. 	}
  39. 	if(dist[n] == 1e18){
  40. 		cout<<-1;
  41. 	}else{
  42. 		cout<<dist[n];
  43. 	}
  44. 	return 0;
  45. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 6
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
4 5 3
1
stdout
copy 
11
https://ideone.com/SZzaZy
language:
C++ (gcc 8.3)
created:
1 day 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!