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