コンテンツにスキップ

ABC477 E - Wheel Distance

サイト
AtCoder
コンテスト
ABC477
問題
E - Wheel Distance
難易度
1235

頂点 1,…,N1, \ldots, N が重み AiA_i の辺で円環状につながり、さらに各頂点 ii が中心の頂点 N+1N+1 と重み BiB_i の辺でつながったグラフがあります。QQ 個のクエリ (S,T)(S, T) それぞれについて、頂点 SS から頂点 TT への最短経路の長さを求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

中心の頂点を H=N+1H = N + 1 とし、HH から各頂点への最短距離 FvF_v をダイクストラ法で求めておきます。

T=HT = H のときは、答えは FSF_S です。

T≠HT \ne H のときは、最短経路が HH を通るかどうかで場合分けします。

  • HH を通る場合: SS から HH へ行き、HH から TT へ行く経路になるので、長さは FS+FTF_S + F_T 以上です。逆に、S→HS \to H と H→TH \to T の最短経路をつなげれば長さ FS+FTF_S + F_T の経路が作れます。なので、この場合の最短は FS+FTF_S + F_T です。
  • HH を通らない場合: 円環の上だけを通るので、SS から TT へ時計回りに行くか、反時計回りに行くかの 2 通りです。AA の累積和を Gi=A1+⋯+AiG_i = A_1 + \cdots + A_i とすると、長さはそれぞれ GT−1−GS−1G_{T-1} - G_{S-1} と GN−(GT−1−GS−1)G_N - (G_{T-1} - G_{S-1}) です。

この 3 つの最小値が答えです。前処理が O(Nlog⁡N)O(N \log N)、各クエリが O(1)O(1) です。

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 始まりで、0,…,N−10, \ldots, N-1 が円環、NN が中心です。

C、D、E に辺の両端と重みを入れ、wgraph の setEdge で重み付き無向グラフを作り、getDist(N, F) で中心からの最短距離を F に求めています。G は AA の累積和です。

クエリでは x<?= (小さい方を代入する cLay の演算子)で 3 つの候補の最小値をとっています。N-T が 00、つまり TT が中心のときは F[S] を出力します。

Python
from heapq import heappop, heappush
from 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 で書いています。