Submission #50732989

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<uint64> l(m), d(m), k(m), c(m), A(m), B(m);
  vector go(n, vector<int>());
  for (int i = 0; i < m; i++) {
    cin >> l[i] >> d[i] >> k[i] >> c[i] >> A[i] >> B[i];
    A[i]--, B[i]--;
    go[B[i]].push_back({i});
  }

  vector<uint64> dist(n);
  dist[n - 1] = numeric_limits<uint64>::max();
  priority_queue<pair<uint64, int>> que;
  que.push({dist[n - 1], n - 1});
  vector<bool> vt(n);
  while (!que.empty()) {
    auto [_, u] = que.top();
    que.pop();
    if (vt[u]) continue;
    vt[u] = true;
    for (int i : go[u]) {
      if (dist[u] < c[i]) continue;
      uint64 v = A[i];
      uint64 t = dist[u] - c[i];
      if (t >= l[i]) {
        uint64 x = (t - l[i]) / d[i];
        ckmin(x, k[i] - 1);
        if (l[i] + x * d[i] > dist[v]) {
          dist[v] = l[i] + x * d[i];
          que.push({dist[v], v});
        }
      }
    }
  }
  for (int i = 0; i < n - 1; i++) {
    if (vt[i]) cout << dist[i] << '\n';
    else cout << "Unreachable\n";
  }

  return 0;
}

Submission Info

Judge Result