fork download
  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. pair<int, int> f[N][2];
  29.  
  30. void dijkstra() {
  31. memset(f, 0x3f, sizeof f);
  32. f[1][0] = f[1][1] = {0, -moneyLim};
  33. priority_queue<tuple<int, int, int, int>> pq;
  34. pq.push({0, moneyLim, 1, 0}); pq.push({0, moneyLim, 1, 1});
  35. while (pq.size()) {
  36. int dist = -get<0>(pq.top()); int money = get<1>(pq.top());
  37. int u = get<2>(pq.top()); int state = get<3>(pq.top());
  38. pq.pop();
  39. if (dist != f[u][state].first || -money != f[u][state].second) 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][0] > make_pair(f[u][state].first + wBike + c, -moneyBike)) {
  51. f[v][0] = {f[u][state].first + wBike + c, -moneyBike};
  52. pq.push({-f[v][0].first, moneyBike, v, 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][1] > make_pair(f[u][state].first + wBus + d, -moneyBus)) {
  63. f[v][1] = {f[u][state].first + wBus + d, -moneyBus};
  64. pq.push({-f[v][1].first, moneyBus, v, 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. ans = min(ans, f[numNode][0].first);
  81. ans = min(ans, f[numNode][1].first);
  82. cout << ans;
  83. }
  84.  
  85. int main() {
  86. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  87.  
  88. #ifdef LOCAL
  89. freopen("main.inp", "r", stdin);
  90. freopen("main.out", "w", stdout);
  91. #else
  92. #define file "name"
  93. if (fopen(file".inp", "r")) {
  94. freopen(file".inp", "r", stdin);
  95. freopen(file".out", "w", stdout);
  96. }
  97. #endif // LOCAL
  98.  
  99. int T; T = 1; if (0) cin >> T;
  100. for (int i = 1; i <= T; i++)
  101. {
  102. solve();
  103. }
  104. }
  105.  
Success #stdin #stdout 0.01s 5292KB
stdin
3 2
1 2 1 99
2 3 99 1
1000
stdout
3