C - Find Parking Lot
Ceylon
3
s
1024
MB
300
点
問題文
筑波大学には $1$ から $N$ までの番号が付けられた $N$ 個の地点と $1$ から $M$ までの番号が付けられた $M$ 個の道路があります。
道路 $i$ は地点 $a_i$ と地点 $b_i$ を双方向に結んでおり、徒歩で移動するのに $c_i$ 分かかります。
自転車に乗っている場合は徒歩の半分の時間で移動できます。
また、$K$ 個の地点 $p_1, p_2, ..., p_K$ には駐輪場があり、それぞれの駐輪場について、空いているスペースを見つけて駐輪するまで $t_1, t_2, ..., t_K$ 分かかります。
今 Ryoga くんは自転車に乗っており、地点 $1$ にいて地点 $N$ に行こうとしています。
次は地点 $N$ で授業なので急いでどこかの駐輪場で自転車を停め、地点 $N$ に行かなくてはなりません。
最短で何分かかりますか。
制約
- $2 \leq N \leq 10^5$
- $1 \leq M \leq \min\left(\frac{N(N - 1)}{2}, 10^5\right)$
- $1 \leq K \leq N$
- $1 \leq a_i, b_i \leq N$
- $a_i \neq b_i$
- $i \neq j$ ならば $(a_i, b_i )\neq (a_j, b_j)$ かつ $(a_i, b_i) \neq (b_j, a_j)$
- $1 \leq c_i \leq 10^9$
- $1 \leq p_i \leq N$
- $1 \leq t_i \leq 10^9$
- $c_i$ は全て偶数
- 入力は全て整数である
- $i\neq j$ ならば $p_i \neq p_j$
- どの地点同士も、いくつかの道路を通って互いに行き来できる
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $K$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_M$ $b_M$ $c_M$
$p_1$ $t_1$
$\vdots$
$p_K$ $t_K$
出力
答えを出力せよ。
入力例 1
4 4 2
1 2 4
1 3 2
2 4 2
3 4 4
2 1
3 2
出力例 1
5
入力例 2
2 1 2
1 2 2
1 10
2 10
出力例 2
11
入力例 3
10 11 4
1 2 4
1 3 6
1 4 8
2 5 6
3 6 4
4 7 2
5 10 8
6 9 4
7 8 2
8 10 4
9 10 6
2 4
6 6
8 4
9 6
出力例 3
14