問題一覧 > 通常問題

No.3810 Binary Shortest Path Query

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 16
作問者 : dyktr_06 / テスター : tyawanmusi sepa38
お気に入りにしたユーザー ProblemId : 14067 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。