fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 2e5 + 5, INF= 1e18+5;
  4. long long n,m, d[MaxN], p[MaxN];
  5. vector<pair<long long, long long>> vt[MaxN];
  6. vector<long long> ans;
  7. void dijikstra(long long v, long long d[])
  8. {
  9.     priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
  10.     pq.push({0,1});
  11.     while(!pq.empty())
  12.     {
  13.         long long u = pq.top().second;
  14.         long long du= pq.top().first;
  15.         pq.pop();
  16.         if(du!=d[u]) continue;
  17.         for (auto x : vt[u])
  18.         {
  19.             long long v = x.first;
  20.             long long weight_v = x.second;
  21.             if(d[v]>d[u]+weight_v)
  22.             {
  23.                 d[v]=d[u]+weight_v;
  24.                 pq.push({d[v],v});
  25.                 p[v]=u;
  26.             }
  27.         }
  28.     }
  29. }
  30. void input()
  31. {
  32.     cin >> n >> m;
  33.     for (long long i=1; i<=m; i++)
  34.     {
  35.         long long u,v,w;
  36.         cin >> u >> v >> w;
  37.         vt[u].push_back ({v,w});
  38.         vt[v].push_back({u,w});
  39.     }
  40. }
  41. void output()
  42. {
  43.     memset(d,0x3f, sizeof(d));
  44.     d[1]=0;
  45.     dijikstra(1,d);
  46.     if(d[n]>INF)
  47.     {
  48.         cout << -1;
  49.         return;
  50.     }
  51.     long long node = n;
  52.     ans.push_back(node);
  53.     while(node!=1)
  54.     {
  55.         node = p[node];
  56.         ans.push_back(node);
  57.     }
  58.     reverse(ans.begin(),ans.end());
  59.     cout << d[n] << "\n";
  60.     for (long long x : ans)
  61.     {
  62.         cout << x << " ";
  63.     }
  64. }
  65. int main()
  66. {
  67.     ios_base::sync_with_stdio(0);
  68.     cin.tie(0);
  69.     input();
  70.     output();
  71. }
  72.  
Success #stdin #stdout 0.01s 11192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/V48LZU
language:
C++14 (gcc 8.3)
created:
3 days 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!