fork download
copy 
  1. /**
  2.  *    author:  mamion
  3.  *    created: Sunday 2024-10-27
  4. **/
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #ifdef LOCAL
  10. #include<cpp-dump-main/cpp-dump.hpp>
  11. #define debug(...) cpp_dump(__VA_ARGS__)
  12. CPP_DUMP_SET_OPTION_GLOBAL(max_line_width, 100);
  13. CPP_DUMP_SET_OPTION_GLOBAL(log_label_func, cpp_dump::log_label::filename());
  14. CPP_DUMP_SET_OPTION_GLOBAL(enable_asterisk, true);
  15. #else
  16. #define debug(...)
  17. #endif // LOCAL
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double ld;
  22.  
  23. const int inf = 1e9;
  24. const int N = 1e4 + 10, M = 1e3 + 10;
  25. int numNode, numEdge, moneyLim;
  26. vector<tuple<int, int, int>> adj[N];
  27.  
  28. int f[N][M][2];
  29.  
  30. void dijkstra() {
  31.     memset(f, 0x3f, sizeof f);
  32.     f[1][moneyLim][0] = f[1][moneyLim][1] = 0;
  33.     priority_queue<tuple<int, int, int, int>> pq;
  34.     pq.push({0, 1, moneyLim, 0}); pq.push({0, 1, moneyLim, 1});
  35.     while (pq.size()) {
  36.         int dist = -get<0>(pq.top()); int u = get<1>(pq.top());
  37.         int money = get<2>(pq.top()); int state = get<3>(pq.top());
  38.         pq.pop();
  39.         if (dist != f[u][money][state]) continue;
  40.         for (auto p : adj[u]) {
  41.             int v = get<0>(p), c = get<1>(p), d = get<2>(p);
  42.             if (state == 1) c++; else d++;
  43.             // go by bike here
  44.             int moneyBike = money, wBike = 0;
  45.             if (moneyBike < c) {
  46.                 moneyBike = min(moneyLim, money + (c - money + 99 - 1) / 99 * 99);
  47.                 wBike = (c - money + 99 - 1) / 99;
  48.             }
  49.             moneyBike -= c;
  50.             if (f[v][moneyBike][0] > f[u][money][state] + wBike + c) {
  51.                 f[v][moneyBike][0] = f[u][money][state] + wBike + c;
  52.                 pq.push({-f[v][moneyBike][0], v, moneyBike, 0});
  53.             }
  54.  
  55.             // go by bus here
  56.             int moneyBus = money, wBus = 0;
  57.             if (moneyBus < d) {
  58.                 moneyBus = min(moneyLim, money + (d - money + 99 - 1) / 99 * 99);
  59.                 wBus = (d - money + 99 - 1) / 99;
  60.             }
  61.             moneyBus -= d;
  62.             if (f[v][moneyBus][1] > f[u][money][state] + wBus + d) {
  63.                 f[v][moneyBus][1] = f[u][money][state] + wBus + d;
  64.                 pq.push({-f[v][moneyBus][1], v, moneyBus, 1});
  65.             }
  66.         }
  67.     }
  68. }
  69.  
  70. void solve() {
  71.     cin >> numNode >> numEdge;
  72.     for (int i = 0; i < numEdge; i++) {
  73.         int u, v, c, d; cin >> u >> v >> c >> d;
  74.         adj[u].push_back({v, c, d});
  75.         adj[v].push_back({u, c, d});
  76.     }
  77.     cin >> moneyLim;
  78.     dijkstra();
  79.     int ans = inf;
  80.     for (int i = 0; i <= moneyLim; i++) {
  81.         ans = min(ans, f[numNode][i][0]);
  82.         ans = min(ans, f[numNode][i][1]);
  83.     }
  84.     cout << ans;
  85. }
  86.  
  87. int main() {
  88.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  89.  
  90. #ifdef LOCAL
  91.     freopen("main.inp", "r", stdin);
  92.     freopen("main.out", "w", stdout);
  93. #else
  94.     #define file "name"
  95.     if (fopen(file".inp", "r")) {
  96.         freopen(file".inp", "r", stdin);
  97.         freopen(file".out", "w", stdout);
  98.     }
  99. #endif // LOCAL
  100.  
  101.     int T; T = 1; if (0) cin >> T;
  102.     for (int i = 1; i <= T; i++)
  103.     {
  104.         solve();
  105.     }
  106. }
  107.  
Success #stdin #stdout 0.02s 82856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000
https://ideone.com/AGm45c
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!