fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #define MOD 1000000007//10e9+7;
  4. #define MAX 100003
  5. #define T() int t; scanf("%d",&t);while(t--)
  6. #define FOR(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
  7. #define RFOR(i,a,b) for(int (i) = (a)-1; (i) >= (b); (i)--)
  8. #define CLEAR(a) memset((a),0,sizeof(a))
  9. #define all(v) v.begin(), v.end()
  10. #define si(x) scanf("%d",&x)
  11. #define sll(x) scanf("%lld",&x)
  12. #define pi(x) printf("%d\n",x)
  13. #define pll(x) printf("%lld\n",x)
  14. #define fi first
  15. #define se second
  16. #define pb push_back
  17. #define mp make_pair
  18. using namespace std;
  19.  
  20. const long long INF =9999999;
  21.  
  22. typedef long long int ll;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vl;
  25. typedef pair<long long,int> pii;
  26. typedef pair<ll,ll> pll;
  27.  
  28. list<pii> adj[MAX];
  29. ll dist[MAX];
  30.  
  31. void dijkstra(int src)
  32. {
  33. 	priority_queue<pii,vector<pii>,greater<pii>> pq;
  34. 	int x,y;
  35. 	ll weight;
  36. 	pii p;
  37. 	memset(dist,INF,sizeof(dist));
  38. 	dist[src] =0;
  39. 	pq.push(mp(0,src));
  40. 	while(!pq.empty())
  41. 	{
  42. 		x = pq.top().se;
  43. 		pq.pop();
  44. 		list< pair<long long, int> >::iterator i;
  45.         for (i = adj[x].begin(); i != adj[x].end(); ++i)
  46. 		{
  47. 			y = (*i).se;
  48. 			weight =(*i).fi;
  49. 			if(dist[x]+weight<dist[y])
  50. 			{
  51. 				dist[y] = dist[x]+weight;
  52. 				pq.push(mp(dist[y],y));
  53. 			}
  54. 		}
  55.  
  56. 	}
  57. }
  58. int main() 
  59. {
  60. 	int nodes,edges;
  61. 	si(nodes);si(edges);
  62. 	int x,y;
  63. 	ll wt;
  64. 	FOR(i,0,edges)
  65. 	{
  66. 		si(x);si(y);sll(wt);
  67. 		adj[x].pb(mp(wt,y));
  68. 		adj[y].pb(mp(wt,x));
  69. 	}
  70. 	dijkstra(1);
  71. 	FOR(i,2,nodes+1)
  72. 	{
  73. 		printf("%lld ",dist[i]);
  74. 	}
  75. 	return 0;
  76. }
Success #stdin #stdout 0s 18368KB
comments (?)
stdin
copy 
5 5
1 2 5
1 3 2
3 4 1
1 4 6
3 5 5
stdout
copy 
5 2 3 7
https://ideone.com/VSqndn
language:
C++14 (gcc 8.3)
created:
7 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!