No.3810 Binary Shortest Path Query
レベル :
/ AI推定難易度 : 1800
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 :
dyktr_06
/ テスター :
tyawanmusi
sepa38
タグ : / 解いたユーザー数 16
作問者 :
sepa38
問題文最終更新日: 2026-11-20 00:00:45
yukicoder contest 524
(順位表)
の他の問題:
問題文
$N$ 頂点 $M$ 辺の無向グラフがあります。頂点には $1$ から $N$ まで、辺には $1$ から $M$ までの番号が付けられています。
辺 $i$ は頂点 $U_i$ と頂点 $V_i$ を双方向に結び、辺を通って移動をするのには $W_i \times 2^i$ の時間がかかります。
また、任意の異なる二つの頂点の間を移動できるワープゲートがあります。頂点 $i$ と頂点 $j$ の間をワープゲートで移動するのには $S_i+S_j$ の時間がかかります。
$Q$ 個のクエリが与えられます。$j$ 番目のクエリでは、頂点 $a_j$ から頂点 $b_j$ まで移動するのにかかる時間の最小値を求めてください。
制約
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq M \leq 2 \times 10^5$
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq U_i < V_i \leq N$
- $0 \leq W_i \leq 10^{18}$
- $0 \leq S_i \leq 10^{18}$
- $1 \leq a_j < b_j \leq N$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
$N$ $M$ $Q$ $S_1$ $S_2$ $\dots$ $S_N$ $U_1$ $V_1$ $W_1$ $U_2$ $V_2$ $W_2$ $\vdots$ $U_M$ $V_M$ $W_M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_Q$ $b_Q$
出力
$Q$ 行出力してください。$j$ 行目には、$j$ 番目のクエリに対する答えを出力してください。
サンプル
サンプル1
入力
4 3 3 10 100 100 10 1 2 1 2 3 1 3 4 100 1 3 1 4 2 4
出力
6 20 22
最初のクエリでは、辺 $1$ と辺 $2$ を順に通ると、かかる時間は $1 \times 2^1+1 \times 2^2=6$ になります。
二つ目のクエリでは、頂点 $1$ から頂点 $4$ へ直接ワープすることで、かかる時間は $S_1+S_4=20$ になります。
サンプル2
入力
5 4 3 1 100 1000 1 1000 1 3 10 3 5 10 2 4 1000 1 5 1000 1 5 2 4 2 5
出力
60 101 161
三つ目のクエリでは、頂点 $2$ から頂点 $1$ へワープした後、辺 $1$ と辺 $2$ を順に通ることで、かかる時間は $161$ になります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。