fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<functional>
  6. #include<utility>
  7. #include<queue>
  8. #include<limits>
  9. #include<cstdio>
  10. using namespace std;
  11. const long long int INF = 100000005;
  12. typedef pair <long long int ,long long int> p;
  13. vector<p> adj[100005];
  14. void dijkstra(long long int x,long long int b);
  15. int main()
  16.   {
  17.   	ios_base::sync_with_stdio(false);
  18.   	long long nodes,t,edges,x,y,weight,a,b;
  19.   	cin>>t;
  20.   	while(t--)
  21.   	{
  22.   	 cin>>nodes>>edges;
  23.   	 for(long long int i=1;i<=edges;i++)
  24.   	  {
  25.   	    cin>>x>>y>>weight;	
  26.   	    adj[x].push_back(make_pair(weight,y));
  27.   	    //adj[y].push_back(make_pair(weight,x));
  28. 	  }
  29. 	  cin>>a>>b;
  30. 	  dijkstra(a,b);
  31. 	  for(long long i = 1; i <= nodes; i++) adj[i].clear();
  32.      }
  33. 	return 0;
  34.   }
  35.  
  36. 	void dijkstra(long long int a,long long int b)
  37.    	{
  38. 	   	priority_queue< p,vector<p>,greater <p> > q;
  39. 	   	long long int cost[100005];
  40. 	   	memset(cost,INF,sizeof(cost));
  41. 	   	q.push(make_pair(0,a));
  42.    	 	cost[a]=0;
  43.    		while(!q.empty())
  44.    	   	{
  45.    	      	p pi=q.top();  //why error
  46.    	      	q.pop();
  47. 		 	long long int u=pi.second;   //vertex
  48. 		  	long long int v=pi.first;    //weight
  49. 		  	if(cost[u]<v)
  50. 		  	continue;
  51. 		  	//check
  52. 		  	for(long long int i=0;i<adj[u].size();i++)
  53. 		  	{
  54. 			   	long long int w=adj[u][i].first;   //edge weight
  55. 		   		long long int x=adj[u][i].second;  //node
  56. 		  		if(cost[x]>cost[u]+w)
  57. 		  	  	{
  58. 			  	   	cost[x]=cost[u]+w;
  59. 					q.push(make_pair(cost[x],x));	
  60. 			  	}
  61. 		  	}
  62. 	   	}
  63. 	   	if(cost[b]>=INF)
  64. 	   	{
  65. 	   	cout<<"NO\n";
  66. 		   	return ;
  67. 	   	}
  68.    		cout<<cost[b]<<"\n";
  69.    	}
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3
stdout
copy 
12
5
NO
https://ideone.com/xZhuTP
language:
C++ (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!