fork(10) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define INF 10000000000000009
  4. #define MAX 100009
  5. #define pii pair <long long ,long long >
  6. #define pb push_back
  7. vector < pii > graph[MAX]; 
  8. long long dist[MAX];
  9. void Reset()
  10. {
  11. 	memset(dist,INF,sizeof(dist));
  12. 	long long i;
  13. 	for(i=0;i<MAX;i++)
  14. 	graph[i].clear();
  15. }
  16. void dijkstra(long long start)
  17. {
  18. 	priority_queue < pii , vector< pii >,greater< pii > > q;	//in the priority queue the greater func is default
  19.  	dist[start]=0;
  20.  	q.push(pii(0,start));	//pushing the starting node
  21.  	long long i,v,w,u,c;
  22.  
  23.  	while(!q.empty())
  24.  	{
  25.  		u=q.top().second;
  26.  		c=q.top().first;
  27.  		q.pop();
  28.  		for(i=0;i<graph[u].size();i++)
  29.  		{
  30.  
  31.  			v=graph[u][i].first;
  32.  			w=graph[u][i].second;
  33.  
  34.  			if(dist[v]>dist[u]+w)
  35.  			{
  36.  				dist[v]=dist[u]+w;
  37.  				q.push(pii(dist[v],v));
  38. 	 		}
  39. 	    }
  40. 	}
  41. }
  42. int main()
  43. {
  44. 	long long i,n,v,u,w,edges,nodes,t,start,destination;
  45. 	scanf("%lld",&t);
  46. 	while(t--)
  47. 	{
  48. 		Reset();
  49. 		scanf("%lld%lld",&nodes,&edges);
  50. 		for(i=1;i<=edges;i++)
  51. 		{
  52. 			scanf("%lld%lld%lld",&v,&u,&w);	//taking the edges as input in a array of paired vectors containing relation,dist
  53. 			//this a directed graph ....make appropriate changes for an undirected graph
  54. 			graph[v].pb(pii(u,w));
  55. 		}
  56. 		scanf("%lld%lld",&start,&destination);
  57. 		dijkstra(start);
  58. 		if(dist[destination]>=INF)
  59. 		printf("NO\n");
  60. 		else
  61. 		printf("%lld\n",dist[destination]);
  62. 	}
  63. 	return 0;
  64. }
Success #stdin #stdout 0s 6344KB
comments (?)
stdin
copy 
2
2 1
1 2 4
1 2
3 3
1 2 3
2 3 10 
1 3 16
1 3
stdout
copy 
4
13
https://ideone.com/K3aA0E
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!