fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 2e5 + 5,MaxK=2, INF= 1e18;
  4. long long n,m, d[MaxN][MaxK];
  5. vector<pair<long long, long long>> vt[MaxN];
  6.  
  7. void dijikstra()
  8. {
  9.     priority_queue<tuple<long long, long long, long long>,
  10.                    vector<tuple<long long, long long, long long>>,
  11.                    greater<tuple<long long, long long, long long>>> pq;
  12.  
  13.     pq.push({0,1,0});
  14.  
  15.     while(!pq.empty())
  16.     {
  17.         long long du=get<0>(pq.top());
  18.         long long u=get<1>(pq.top());
  19.         long long state=get<2>(pq.top());
  20.         pq.pop();
  21.  
  22.         if(du!=d[u][state]) continue;
  23.  
  24.         for(auto x:vt[u])
  25.         {
  26.             long long v=x.first;
  27.             long long weight_v=x.second;
  28.             long long nd=du+weight_v;
  29.  
  30.             if(state==0)
  31.             {
  32.                 if(nd<d[v][0])
  33.                 {
  34.                     d[v][1]=d[v][0];
  35.                     d[v][0]=nd;
  36.  
  37.                     pq.push({d[v][0],v,0});
  38.  
  39.                     if(d[v][1]!=INF)
  40.                         pq.push({d[v][1],v,1});
  41.                 }
  42.                 else if(d[v][0]<nd && nd<d[v][1])
  43.                 {
  44.                     d[v][1]=nd;
  45.                     pq.push({d[v][1],v,1});
  46.                 }
  47.             }
  48.  
  49.             if(state==1)
  50.             {
  51.                 if(d[v][0]<nd && nd<d[v][1])
  52.                 {
  53.                     d[v][1]=nd;
  54.                     pq.push({d[v][1],v,1});
  55.                 }
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. void input()
  62. {
  63.     cin>>n>>m;
  64.  
  65.     for(long long i=1;i<=m;i++)
  66.     {
  67.         long long u,v,w;
  68.         cin>>u>>v>>w;
  69.  
  70.         vt[u].push_back({v,w});
  71.         vt[v].push_back({u,w});
  72.     }
  73. }
  74.  
  75. void output()
  76. {
  77.     for(long long i=1;i<=n;i++)
  78.     {
  79.         for(long long j=0;j<=1;j++)
  80.         {
  81.             d[i][j]=INF;
  82.         }
  83.     }
  84.  
  85.     d[1][0]=0;
  86.  
  87.     dijikstra();
  88.  
  89.     if(d[n][1]==INF)
  90.     {
  91.         cout<<-1;
  92.         return;
  93.     }
  94.  
  95.     cout<<d[n][1];
  96. }
  97.  
  98. int main()
  99. {
  100.     ios_base::sync_with_stdio(0);
  101.     cin.tie(0);
  102.  
  103.     input();
  104.     output();
  105. }
Success #stdin #stdout 0.01s 10180KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2551Fa
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!