fork(4) download
  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
stdin
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
stdout
1 2 5