fork(6) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define scan(a) scanf("%d",&a)
  5. #define r5 100005
  6. #define f(i,a,b) for(i=a;i<b;i++)
  7. #define print(a) printf("%d\n",a)
  8. #define pb push_back
  9. #define nl printf("\n");
  10. #define inf INT_MAX
  11. typedef long long int lli;
  12. typedef pair<int,int> ii;
  13. vector< ii > adj[r5];
  14. set< ii > q;
  15. int dist[r5];
  16.  
  17. int main(){
  18. 	int t;
  19. 	scan(t);
  20. 	while(t--){
  21. 		q.clear();
  22. 		int V,E,mx=0,i,j,a,b,c,start,end;
  23. 		scan(V);
  24. 		scan(E);
  25.  
  26. 		f(i,0,V+100){
  27. 			dist[i]=inf;
  28. 			adj[i].clear();
  29. 		}
  30.  
  31. 		f(i,0,E){
  32. 			scan(a);
  33. 			scan(b);
  34. 			scan(c);
  35. 			adj[a].pb(ii(b,c));
  36. 		}
  37. 		scanf("%d%d",&start,&end);
  38.  
  39. 		//dijstra
  40.  
  41. 		dist[start]=0;
  42. 		q.insert(ii(0,start));
  43. 		vector< ii >::iterator it;
  44.  
  45. 		while(!q.empty()){
  46. 			ii top=*q.begin();
  47. 			int d=top.first,u=top.second;
  48. 			q.erase(q.begin());
  49. 			f(it,adj[u].begin(),adj[u].end())
  50. 			{
  51. 				int v=it->first,cost=it->second;
  52. 				if(dist[v]>dist[u]+cost){
  53. 					if(dist[v]!=inf){
  54. 						q.erase(q.find(ii(dist[v],v)));
  55. 					}
  56. 					dist[v]=dist[u]+cost;
  57. 					q.insert(ii(dist[v],v));
  58. 				}
  59. 			}
  60. 		}
  61.  
  62. 		if(dist[end]<inf)
  63. 		print(dist[end]);
  64. 		else
  65. 		printf("NO\n");
  66. 	}
  67. 	return 0;
  68. }
  69.  
Success #stdin #stdout 0s 4840KB
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/mTknF4
language:
C++ (gcc 8.3)
created:
9 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!