ABC477 E - Wheel Distance

車輪の距離

考え方

グラフの形は、タイトルのように車輪の形である。
つまり、中心に頂点 $N+1$ があり、残りの $N$ 点が円周上にあると思うことができる。

この場合、円周上の $2$ 点 $P,Q$ 間の最短経路は、以下の $3$ つのいずれかである。

上の $2$ つは、円周上の距離の累積和を事前に求めておけば、$O(1)$ で処理できる。
最後のものは、中心から各点までの最短距離をDijkstra法で求めておけば、やはり $O(1)$ で処理できる。

また、片方が中心だった場合も、中心から各点までの最短距離を求めておけばそれを答えるだけ。

ということで、累積和とDijkstra法の事前処理のもと、どんなクエリでも $O(1)$ で処理できる。

事前処理分も含めて、全体として $O(N\log N+Q)$ である。

入力を受け取る。

n: 5
q: 3
a: {1, 3, 4, 2, 5}
b: {5, 2, 4, 3, 7}
queries:
2 5
5 6
1 4

円周上の辺の距離 a の累積和は、次のようになる。

sum: {0, 1, 4, 8, 10, 15}

次に、中心の頂点 $6$ から Dijkstra法を行う。
各頂点までの最短距離と、その最短経路の一例は次のようになる。

頂点	$1$	$2$	$3$	$4$	$5$	$6$
最短距離	$3$	$2$	$4$	$3$	$5$	$0$
最短経路の一例	$6\to2\to1$	$6\to2$	$6\to3$	$6\to4$	$6\to4\to5$	$6$

この $2$ つの前処理を使って、各クエリの候補を求める。

クエリ	時計回り	反時計回り	中心経由・中心まで	最短距離
`2 5`	$10-1=9$	$(15-10)+1=6$	$2+5=7$	$6$
`5 6`	-	-	$5$	$5$
`1 4`	$8-0=8$	$(15-8)+0=7$	$3+3=6$	$6$

したがって、$3$ つのクエリの答えは順に $6,5,6$ となる。

円周上の距離の累積和や最短距離は、int 型からはみ出る可能性がある。
long long 型を用いること。

特になし。