Submission #50587352

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int n, m;
  cin >> n >> m;
  vector<int> l(m), d(m), k(m), c(m), a(m), b(m);
  vector<vector<int>> g(n);
  for (int i = 0; i < m; ++i) {
    cin >> l[i] >> d[i] >> k[i] >> c[i] >> a[i] >> b[i];
    --a[i], --b[i];
    g[b[i]].push_back(i);
  }
  vector<long long> dist(n, -1);
  dist[n - 1] = 2e18;
  priority_queue<pair<long long, int>> q;
  q.emplace(dist[n - 1], n - 1);
  vector<char> used(n);
  while (!q.empty()) {
    auto [_, v] = q.top();
    q.pop();
    if (used[v]) continue;
    used[v] = true;
    for (int i : g[v]) {
      if (dist[v] < l[i] + c[i]) continue;
      int x = min<long long>(k[i] - 1, (dist[v] - l[i] - c[i]) / d[i]);
      long long y = l[i] + 1ll * x * d[i];
      if (dist[a[i]] < y) {
        dist[a[i]] = y;
        q.emplace(y, a[i]);
      }
    }
  }
  for (int i = 0; i < n - 1; ++i) {
    if (dist[i] == -1) cout << "Unreachable";
    else cout << dist[i];
    cout << '\n';
  }

  return 0;
}

Submission Info

Judge Result