fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pii pair<int,int>
  4. #define pb push_back
  5. #define inf 0x7fffffff
  6. #define maxx 100009
  7. priority_queue<pii,vector<pii>,greater<pii> >q;
  8. vector<pii>G[maxx];
  9. int d[maxx];
  10. bool f[maxx];
  11. int prevv[maxx];
  12. int n,m;
  13. void printpath(int src)
  14. {
  15. 	if(prevv[src]!=-1)
  16. 	printpath(prevv[src]);
  17. 	cout<<src<<" ";
  18. }
  19. void dijktras(int src)
  20. {
  21.    for(int i=0;i<=n;i++)
  22.    {
  23.    	d[i]=inf;
  24.    	f[i]=false;
  25.    	prevv[i]=-1;
  26.    }
  27.    d[src]=0;
  28.    q.push(pii(src,0));
  29.    while(!q.empty())
  30.    {
  31.    	 int s=q.top().first;
  32.    	 q.pop();
  33.    	 for(int i=0;i<G[s].size();i++)
  34.    	 {
  35.    	 	int v=G[s][i].first;
  36.    	 	int w=G[s][i].second;
  37.    	 	if(!f[v] && d[s]+w<d[v])
  38.    	 	{
  39.    	 		d[v]=d[s]+w;
  40.    	 		q.push(pii(v,d[v]));
  41.    	 		prevv[v]=s;
  42.    	 	}
  43.    	 }
  44.    	 f[s]=true;
  45.    }
  46. }
  47. int main() {
  48. 	// your code goes here
  49. 	memset(prevv,-1,sizeof prevv);
  50. 	cin>>n>>m;
  51. 	while(m--)
  52. 	{
  53. 		int a,b,w;
  54. 		cin>>a>>b>>w;
  55. 		G[a].pb(pii(b,w));
  56. 		G[b].pb(pii(a,w));
  57. 	}
  58. 	 dijktras(1);
  59. 	if(d[n]==inf)
  60. 	{
  61. 		cout<<"-1"<<endl;
  62. 	}
  63. 	else
  64. 	printpath(n);
  65. 	return 0;
  66. }
  67.  
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
stdout
copy 
1 2 5
https://ideone.com/d47g3K
language:
C++14 (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!