fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 2e5 + 5,MaxK=10, INF= 1e18;
  4. long long n,m,k, d[MaxN][MaxK];
  5. vector<pair<long long, long long>> vt[MaxN];
  6. void dijikstra(long long v)
  7. {
  8.     priority_queue<tuple<long long, long long, long long>, vector<tuple<long long, long long, long long>>, greater<tuple<long long, long long, long long>>> pq;
  9.     pq.push({0,1,0});
  10.     while(!pq.empty())
  11.     {
  12.         long long du= get<0>(pq.top());
  13.         long long u = get<1>(pq.top());
  14.         long long state= get<2> (pq.top());
  15.         pq.pop();
  16.         if(du!=d[u][state]) 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][state]>d[u][state]+weight_v)
  22.             {
  23.                 d[v][state]=d[u][state]+weight_v;
  24.                 pq.push({d[v][state],v,state});
  25.             }
  26.             if(state<k&&d[v][state+1]>d[u][state])
  27.             {
  28.                 d[v][state+1]=d[u][state];
  29.                 pq.push({d[v][state+1],v,state+1});
  30.             }
  31.         }
  32.     }
  33. }
  34. void input()
  35. {
  36.     cin >> n >> m >> k;
  37.     for (long long i=1; i<=m; i++)
  38.     {
  39.         long long u,v,w;
  40.         cin >> u >> v >> w;
  41.         vt[u].push_back ({v,w});
  42.         vt[v].push_back({u,w});
  43.     }
  44. }
  45. void output()
  46. {
  47.     for (long long i=1; i<=n; i++)
  48.     {
  49.         for (long long j=0; j<=k; j++)
  50.         {
  51.             d[i][j]=INF;
  52.         }
  53.     }
  54.     d[1][0]=0;
  55.     dijikstra(1);
  56.     long long ans= INF;
  57.     for(long long i=0; i<=k; i++)
  58.     {
  59.         ans=min(d[n][i],ans);
  60.     }
  61.     if(ans==INF)
  62.     {
  63.         cout << -1;
  64.         return;
  65.     }
  66.     cout << ans;
  67. }
  68. int main()
  69. {
  70.     ios_base::sync_with_stdio(0);
  71.     cin.tie(0);
  72.     input();
  73.     output();
  74. }
  75.  
  76.  
Success #stdin #stdout 0.01s 10112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gO1bwQ
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!