fork(1) download
copy 
  1. #include<iostream>
  2. #include<string.h>
  3. #include<queue>
  4. #include<vector>
  5. #define max 22000
  6. #define infinity 999999999
  7. int status[max];
  8. int dist[max];
  9. int tst,n,m,s,t,wt;
  10. struct st
  11. {
  12. 	int v;
  13. 	unsigned int w;
  14. };
  15. class compare
  16. {
  17. 	public:
  18. 	bool operator()(const st& v1,const st& v2)
  19. 	{
  20. 		return v1.w>v2.w;
  21. 	}
  22. };
  23. using namespace std;
  24. priority_queue<st,vector<st>,compare> pq;
  25. vector<st> adj[max];
  26. void dijkstra()
  27. {
  28. 	for(int i=0;i<n;i++)
  29. 	{
  30. 		dist[i]=infinity;
  31. 	}
  32. 	dist[s]=0;
  33. 	st s1={s,dist[s]};
  34. 	pq.push(s1);
  35. 	while(!pq.empty())
  36. 	{
  37. 		st cv=pq.top();
  38. 		pq.pop();
  39. 		status[cv.v]=1;
  40. 		int size=adj[cv.v].size();
  41. 		for(int i=0;i<size;i++)
  42. 		{
  43. 			int u=adj[cv.v][i].v;
  44. 			int w=adj[cv.v][i].w;
  45. 			if(dist[u]>dist[cv.v]+w)
  46. 			{
  47. 				dist[u]=dist[cv.v]+w;
  48. 				if(status[u]==0)
  49. 				{
  50. 					st s1={u,dist[u]};
  51. 					pq.push(s1);
  52. 				}
  53.  
  54. 			}
  55.  
  56.  
  57. 		}
  58. 	}
  59. }
  60. int main()
  61. { 
  62.     cin>>tst;int k=0;
  63.     int v1,v2;
  64.     while(tst--)
  65.     {
  66.     	 cin>>n>>m>>s>>t;
  67.     	 memset(status,0,sizeof(status));
  68.     	 k++;
  69.     	 for(int i=0;i<m;i++)
  70.     	 {
  71.     	 	cin>>v1>>v2>>wt;
  72.     	 	st s1={v2,wt};
  73.     	 	adj[v1].push_back(s1);
  74.     	 	st s2={v1,wt};
  75.     	 	adj[v2].push_back(s2);
  76.     	 }
  77.     	 dijkstra();
  78.     	 int l=dist[t];
  79.     	 if(dist[t]==infinity)
  80.     	 {
  81.     	 	cout<<"Case #"<<k<<": unreachable"<<"\n";
  82.  
  83.     	 }
  84.     	 else
  85.     	 {
  86.     	    cout<<"Case #"<<k<<": "<<l<<"\n";
  87.     	 }
  88.     	 for(int i=0;i<n;i++)
  89.     	 {
  90.     	 	adj[i].clear();
  91.     	 }
  92.     }
  93.     return 0;
  94.  
  95. }
Success #stdin #stdout 0s 3864KB
comments (?)
stdin
copy 
5
20 15 0 5 
0 1 574
0 1 225
0 1 258
0 2 14
0 3 568 
0 3 666
1 3 56
2 3 555
1 4 1
1 4 0
3 4 2222
3 4 22
3 5 1
4 5 444
3 5 222
20 15 4 3 
0 1 574
0 1 225
0 1 258
0 2 14
0 3 568 
0 3 666
1 3 56
2 3 555
1 4 1
1 4 0
3 4 2222
3 4 22
3 5 1
4 5 444
3 5 222
20 15 0 12 
0 1 574
0 1 225
0 1 258
0 2 14
0 3 568 
0 3 666
1 3 56
2 3 555
1 4 1
1 4 0
3 4 2222
3 4 22
3 5 1
4 5 444
3 5 222
20 15 0 0 
0 1 574
0 1 225
0 1 258
0 2 14
0 3 568 
0 3 666
1 3 56
2 3 555
1 4 1
1 4 0
3 4 2222
3 4 22
3 5 1
4 5 444
3 5 222
20 15 5 0
0 1 574
0 1 225
0 1 258
0 2 14
0 3 568 
0 3 666
1 3 56
2 3 555
1 4 1
1 4 0
3 4 2222
3 4 22
3 5 1
4 5 444
3 5 222
stdout
copy 
Case #1: 248
Case #2: 22
Case #3: unreachable
Case #4: 0
Case #5: 248
https://ideone.com/fEGjgN
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!