ABC477 E - Wheel Distance
- サイト
- AtCoder
- コンテスト
- ABC477
- 問題
- E - Wheel Distance
- 難易度
- 1235
頂点 が重み の辺で円環状につながり、さらに各頂点 が中心の頂点 と重み の辺でつながったグラフがあります。 個のクエリ それぞれについて、頂点 から頂点 への最短経路の長さを求める問題です()。
中心の頂点を とし、 から各頂点への最短距離 をダイクストラ法で求めておきます。
のときは、答えは です。
のときは、最短経路が を通るかどうかで場合分けします。
- を通る場合: から へ行き、 から へ行く経路になるので、長さは 以上です。逆に、 と の最短経路をつなげれば長さ の経路が作れます。なので、この場合の最短は です。
- を通らない場合: 円環の上だけを通るので、 から へ時計回りに行くか、反時計回りに行くかの 2 通りです。 の累積和を とすると、長さはそれぞれ と です。
この 3 つの最小値が答えです。前処理が 、各クエリが です。
cLay
ll@N,@Q,@A[N],@B[N],E[2N],F[N+1],G[N+1]{};int C[2N],D[2N];rep(i,N)C[i]=i,D[i]=(i+1)%N,G[i+1]=G[i]+(E[i]=A[i]),C[N+i]=i,D[N+i]=N,E[N+i]=B[i];wgraph<ll>g;g.setEdge(N+1,2N,C,D,E);g.getDist(N,F);rep(Q){ll@S--,@T--,x;if(N-T)x=F[S]+F[T],x<?=G[T]-G[S],wt(x<?=G[S]+G[N]-G[T]);else wt(F[S]);}cLay で書いています。頂点は 0 始まりで、 が円環、 が中心です。
C、D、E に辺の両端と重みを入れ、wgraph の setEdge で重み付き無向グラフを作り、getDist(N, F) で中心からの最短距離を F に求めています。G は の累積和です。
クエリでは x<?= (小さい方を代入する cLay の演算子)で 3 つの候補の最小値をとっています。N-T が 、つまり が中心のときは F[S] を出力します。
Python
from heapq import heappop, heappushfrom itertools import accumulate
N, Q = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split()))graph = [[] for _ in range(N + 1)]for i in range(N): graph[i].append(((i + 1) % N, A[i])) graph[(i + 1) % N].append((i, A[i])) graph[i].append((N, B[i])) graph[N].append((i, B[i]))F = [None] * (N + 1)pq = [(0, N)]while pq: d, v = heappop(pq) if F[v] is not None: continue F[v] = d for u, w in graph[v]: if F[u] is None: heappush(pq, (d + w, u))acc = [0, *accumulate(A)]ans = []for _ in range(Q): S, T = map(int, input().split()) S -= 1 T -= 1 if T == N: ans.append(F[S]) else: ans.append(min(F[S] + F[T], acc[T] - acc[S], acc[S] + acc[N] - acc[T]))print(*ans, sep="\n")cLay 版と同じ処理です。ダイクストラ法は heapq で書いています。