第2回 ドワンゴからの挑戦状 予選 C: メンテナンス明け

問題

C: メンテナンス明け - 第2回 ドワンゴからの挑戦状 予選 | AtCoder

解法

第2回 ドワンゴからの挑戦状 予選 C - メンテナンス明け - うさぎ小屋

コード

#include <bits/stdc++.h>
using namespace std;
typedef pair<int64_t, int> P;

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

  int N, M, s, g;
  cin >> N >> M >> s >> g;
  vector<vector<tuple<int, int64_t, int, int64_t>>> graph(N);
  while (M--) {
    int L;
    cin >> L;
    vector<int> l(L);
    vector<int64_t> w(L - 1);
    for (int li = 0; li < L; ++li) {
      cin >> l[li];
    }
    for (int wi = 0; wi < L - 1; ++wi) cin >> w[wi];
    int64_t sum = accumulate(w.begin(), w.end(), 0LL);
    int64_t accum = 0;
    for (int j = 0; j < L - 1; ++j) {
      graph[l[j]].emplace_back(l[j + 1], w[j], l.back(), sum - accum);
      accum += w[j];
      graph[l[j + 1]].emplace_back(l[j], w[j], l.front(), accum);
    }
  }

  vector<int64_t> dist(N, 1e18);
  priority_queue<P, vector<P>, greater<P>> que;
  que.emplace(0, g);
  dist[g] = 0;
  while (!que.empty()) {
    int64_t now;
    int v;
    tie(now, v) = que.top();
    que.pop();
    for (const auto &t : graph[v]) {
      int u, terminal;
      int64_t w, tw;
      tie(u, w, terminal, tw) = t;
      if (dist[u] <= dist[v] + w) continue;
      dist[u] = dist[v] + w;
      que.emplace(dist[u], u);
    }
  }

  int64_t high = 1e18, low = 0;
  while (high - low > 1) {
    int64_t mid = (high + low) / 2;
    vector<int64_t> forward_dist(N, 1e18);
    forward_dist[s] = 0;
    que.emplace(0, s);
    while (!que.empty()) {
      int v;
      int64_t now;
      tie(now, v) = que.top();
      que.pop();
      for (const auto &t : graph[v]) {
        int u, terminal;
        int64_t w, w_terminal;
        tie(u, w, terminal, w_terminal) = t;
        int64_t asleep = now + w_terminal + dist[terminal];
        int64_t next = now + w;
        if (asleep <= mid && next < forward_dist[u]) {
          forward_dist[u] = next;
          que.emplace(next, u);
        }
      }
    }
    (forward_dist[g] == 1e18 ? low : high) = mid;
  }
  cout << high << endl;
}