fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long LL;
  6. typedef pair<LL,int> II;
  7. const LL inf=2e17;
  8. const int mx=1e5+5;
  9. vector<vector<int> > g(mx),c(mx);
  10. set<II> pq;
  11. vector<int> path;
  12. bitset<mx> visited;
  13. int n,m;
  14. int p[mx];
  15. LL dist[mx];
  16.  
  17. void clr(){
  18.     for(int i=0; i<mx; ++i){
  19.         g[i].clear();
  20.         c[i].clear();
  21.     }
  22.     pq.clear();
  23.     path.clear();
  24.     visited.reset();
  25. }
  26.  
  27. void init(){
  28.     for(int i=0; i<=n; ++i){
  29.         dist[i]=inf;
  30.         p[i]=-1;
  31.     }
  32.     dist[1]=0;
  33. }
  34.  
  35. void dijkstra(){
  36.     init();
  37.     pq.insert({dist[1],1});
  38.     while(!pq.empty()){
  39.         int node=pq.begin()->second;
  40.         int cost=pq.begin()->first;
  41.         pq.erase(pq.begin());
  42.  
  43.         if(node==n) break;
  44.  
  45.         vector<int> v=g[node];
  46.         vector<int> w=c[node];
  47.  
  48.         for(int i=0; i<v.size(); ++i){
  49.             if(dist[v[i]]>(LL)cost+w[i]){
  50.                 II x(dist[v[i]],v[i]);
  51.                 auto it=pq.find(x);
  52.                 if(it!=pq.end()){
  53.                     pq.erase(it);
  54.                 }
  55.                 dist[v[i]]=(LL)cost+w[i];
  56.                 p[v[i]]=node;
  57.  
  58.                 pq.insert({dist[v[i]],v[i]});
  59.             }
  60.         }
  61.     }
  62.  
  63.     int x=n;
  64.     while(true){
  65.         path.push_back(x);
  66.         x=p[x];
  67.         if(x==-1) break;
  68.     }
  69. }
  70.  
  71. void dfs(int node){
  72.     visited[node]=1;
  73.  
  74.     vector<int> v=g[node];
  75.     for(int i=0; i<v.size(); ++i){
  76.         if(!visited[v[i]]){
  77.             dfs(v[i]);
  78.         }
  79.     }
  80. }
  81.  
  82. int main()
  83. {
  84. //    freopen("in.txt","r",stdin);
  85. //    freopen("out.txt","w",stdout);
  86.  
  87.     while(cin>>n>>m){
  88.         clr();
  89.  
  90.         for(int i=0; i<m; ++i){
  91.             int u,v,w;
  92.             cin>>u>>v>>w;
  93.  
  94.             g[u].push_back(v);
  95.             g[v].push_back(u);
  96.  
  97.             c[u].push_back(w);
  98.             c[v].push_back(w);
  99.         }
  100.  
  101.         dfs(1);
  102.         if(!visited[n]){
  103.             cout<<-1<<endl;
  104.             continue;
  105.         }
  106.  
  107.         dijkstra();
  108.  
  109.         for(int i=path.size()-1; i>=0; --i){
  110.             cout<<path[i]<<" ";
  111.         }
  112.         cout<<endl;
  113.     }
  114.  
  115.     return 0;
  116. }
Success #stdin #stdout 0s 17256KB
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 4 3 5
https://ideone.com/2vNqOS
language:
C++14 (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!