コード
#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;
}