第2回 ドワンゴからの挑戦状 予選 C - メンテナンス明け
解法
二分探索します。
ok(x) = (時間 x 以下で目的地にたどり着けるか) を判定する関数を作ります。
そのために, ダイクストラのようなことをしますが, ある頂点 v に時間 t にたどり着けることがわかったとして, v から伸びている辺 e を使える条件は, 「e を含む路線を使って寝過ごしたとして, 寝過ごしてついた終点から目的地に x 以内にたどり着ける」というのが必要十分です。
予めすべての辺を使ったグラフ G についてダイクストラして, 終点までの距離を調べておけば, この条件は, t + (v からその路線の終点までにかかる時間) + (終点から目的地までの最短時間) <= x で判定できます。
で, 目的地までにかかる時間が x 以下なら ok, そうでないなら ng です。
const ll INF = 1ll<<55; struct edge { int v; ll w; edge() {} edge(int v, ll w) : v(v), w(w) {}; }; vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) { vector<ll> d(n, LLONG_MAX/10); d[s] = 0; priority_queue<pair<ll, int> > que; que.push(make_pair(0ll, s)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second; ll dist = -p.first; if (dist > d[u]) continue; for (edge e : G[u]) { if (d[e.v] > d[u]+e.w) { d[e.v] = d[u] + e.w; que.push(make_pair(-d[e.v], e.v)); } } } return d; } struct Edge { int v; ll w; int end; ll sum; Edge() {} Edge(int v, ll w, int end, ll sum) : v(v), w(w), end(end), sum(sum) {} }; const int MAXM = 255555; int N, M, src, dst; vi s[MAXM]; vll w[MAXM], sumW[MAXM][2]; vector<ll> d0; bool ok(ll x, int n, vector<vector<Edge> > G) { vector<ll> d(n, LLONG_MAX/10); d[src] = 0; priority_queue<pair<ll, int> > que; que.push(make_pair(0ll, src)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second; ll dist = -p.first; if (dist > d[u]) continue; for (Edge e : G[u]) { if (dist + e.sum + d0[e.end] > x) continue; if (d[e.v] > d[u]+e.w) { d[e.v] = d[u] + e.w; que.push(make_pair(-d[e.v], e.v)); } } } return x >= d[dst]; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> src >> dst; for (int i = 0; i < M; i++) { int L; cin >> L; s[i].resize(L); w[i].resize(L-1); sumW[i][0].resize(L); sumW[i][1].resize(L); for (int j = 0; j < L; j++) cin >> s[i][j]; for (int j = 0; j < L-1; j++) cin >> w[i][j]; sumW[i][0][0] = 0; for (int j = 0; j < L-1; j++) sumW[i][0][j+1] = sumW[i][0][j] + w[i][j]; sumW[i][1][L-1] = 0; for (int j = L-1; j > 0; j--) sumW[i][1][j-1] = sumW[i][1][j] + w[i][j-1]; } // まずチェック用のダイクストラ vector<vector<edge> > G(N); for (int i = 0; i < M; i++) { int L = s[i].size(); for (int j = 0; j < L-1; j++) { G[s[i][j]].emplace_back(s[i][j+1], w[i][j]); G[s[i][j+1]].emplace_back(s[i][j], w[i][j]); } } d0 = dijkstra(N, G, dst); // グラフその 2 vector<vector<Edge> > Graph(N); for (int i = 0; i < M; i++) { int L = s[i].size(); for (int j = 0; j < L-1; j++) Graph[s[i][j]].emplace_back(s[i][j+1], w[i][j], s[i][L-1], sumW[i][0][L-1]-sumW[i][0][j]); for (int j = L-1; j > 0; j--) Graph[s[i][j]].emplace_back(s[i][j-1], w[i][j-1], s[i][0], sumW[i][1][0]-sumW[i][1][j]); } ll low = 0, high = INF; while (high - low > 1) { ll med = (high+low) / 2; if (ok(med, N, Graph)) high = med; else low = med; } cout << high << endl; return 0; }