fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ii pair<int, int>
  5. #define iii pair<double, pair<int, int>>
  6. #define fi first
  7. #define se second
  8. const int MAXN = 1e5+5;
  9. const int MAXK = 12;
  10. const double INF = 1e18;
  11. int n, m, k, x, y, c;
  12. vector<ii> a[MAXN];
  13.  
  14. double dist[MAXN][MAXK];
  15. void dijk(int s)
  16. {
  17.     for ( int i = 1; i <= n; i++ )
  18.         for ( int j = 0; j <= k; j++ )
  19.             dist[i][j] = INF;
  20.     priority_queue<iii, vector<iii>, greater<iii>> q;
  21.     dist[s][0] = 0;
  22.     q.push({0.0, {0, s}});
  23.     while (!q.empty())
  24.     {
  25.         double cost = q.top().fi;
  26.         int K = q.top().se.fi, u = q.top().se.se;
  27.         q.pop();
  28.         if ( u == n )
  29.         {
  30.             cout << fixed << setprecision(2) << cost;
  31.             exit(0);
  32.         }
  33.         if ( cost > dist[u][K] ) continue;
  34.         for ( ii e : a[u] )
  35.         {
  36.             double vcost = e.se;
  37.             int v = e.fi;
  38.             int power2 = 1;
  39.             for ( int i = 0; K + i <= k; i++ )
  40.             {
  41.                 if ( cost + vcost/power2 < dist[v][K+i] )
  42.                 {
  43.                     dist[v][K+i] = cost + vcost/power2;
  44.                     q.push({dist[v][K+i], {K+i, v}});
  45.                 }
  46.                 power2*=2;
  47.             }
  48.         }
  49.     }
  50. }
  51.  
  52. int main()
  53. {
  54.     ios::sync_with_stdio(0); cin.tie(0);
  55.     cin >> n >> m >> k;
  56.     for ( int i = 1; i <= m; i++ )
  57.     {
  58.         cin >> x >> y >> c;
  59.         a[x].push_back({y, c});
  60.         a[y].push_back({x, c});
  61.     }
  62.     dijk(1);
  63.   return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 7352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R4RUHK
language:
C++14 (gcc 8.3)
created:
4 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!