fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAXN 10000
  4. int M,N;
  5. vector<pair<int, int> > adj[MAXN];
  6. long long dist[MAXN];
  7. int visto[MAXN];
  8.  
  9. void dijkstra(int inizio,int fine){
  10. 	int u;
  11. 	for(u=0; u<=N; u++) dist[u]=9999999999999;
  12. 	dist[inizio]=0;
  13. 	priority_queue<pair<int, int> > pq;
  14. 	pq.push(make_pair(0,inizio));
  15. 	while(!pq.empty()){
  16. 		int s=pq.top().second;
  17. 		pq.pop();
  18. 		if(s==fine) break;
  19. 		if(visto[s]) continue;
  20. 		visto[s]=1;
  21.  
  22. 		for(u=0;u<adj[s].size();u++){
  23. 			int next = adj[s][u].second;
  24. 			int Peso = adj[s][u].first;
  25.  
  26. 			if(dist[s]+Peso<dist[next]){
  27. 				dist[next] = dist[s]+Peso;
  28. 				pq.push(make_pair(-dist[next], next));
  29. 			}
  30. 		}
  31. 	}
  32.  
  33. }
  34.  
  35. int main(void)
  36. {
  37. 	int i,rad, end;
  38. 	int a,b,w;
  39. 	cin >> N >> M;
  40. 	cin >> rad >> end;
  41. 	for(i=0;i<M; ++i){
  42. 		cin >> a >> b >> w;
  43. 		adj[a].push_back(make_pair(w,b));
  44. 	}
  45. 	int u;
  46. 	dijkstra(rad,end);
  47. 	cout << dist[end] << endl;
  48. return 0;
  49. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
4 5
0 1 1
0 2 2
1 3 1
2 1 3
2 3 5
stdout
copy 
9999999999999
https://ideone.com/JkfivE
language:
C++ (gcc 8.3)
created:
2 days 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!