D - 街歩きと通行料 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、ある都市の街並みを散策しています。この都市には N 個の交差点があり、交差点同士は双方向に通行可能な道路で結ばれています。道路は全部で M 本あり、それぞれの道路には移動にかかる所要時間が設定されています。同じ交差点の組を結ぶ道路が複数存在することもありますが、同じ交差点を両端とする道路（自己ループ）は存在しません。

この都市には K 箇所の料金所があり、それぞれ異なる交差点に設置されています。j 番目の料金所は交差点 L_j に設置されており、通行料は C_j です。料金所が設置されていない交差点では通行料はかかりません。

高橋君は交差点 1 から交差点 N まで移動したいと考えています。高橋君は道路を通って交差点から交差点へ移動しますが、同じ交差点や同じ道路を複数回通ってもかまいません。

高橋君の移動経路は、交差点の列 v_0, v_1, v_2, \ldots, v_s（ただし v_0 = 1、v_s = N）として表されます。ここで、連続する 2 つの交差点 v_{k-1} と v_k（1 \leq k \leq s）は道路で直接結ばれていなければなりません。

移動にかかる総コストは、以下の 2 つの合計です。

  • 通った道路の所要時間の合計。すなわち、v_{k-1} と v_k を結ぶ道路として選んだ道路の所要時間を k = 1, 2, \ldots, s について合計したもの。同じ道路を複数回通った場合はその回数分加算する。
  • 経路上の各交差点に設置されている料金所の通行料の合計。すなわち、v_0, v_1, \ldots, v_s の各交差点について、その交差点に料金所がある場合は通行料を加算する。同じ交差点が経路上に複数回現れる場合はその回数分加算する。出発地点（交差点 1）および到着地点（交差点 N）も対象に含まれる。

高橋君が交差点 1 から交差点 N まで移動するときの総コストの最小値を求めてください。なお、交差点 1 から交差点 N へ到達可能であることは保証されます。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq N
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
  • 1 \leq L_j \leq N (1 \leq j \leq K)
  • L_j はすべて異なる (1 \leq j \leq K)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq K)
  • 交差点 1 から交差点 N へ到達可能である
  • 入力はすべて整数である

入力

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
L_1 C_1
L_2 C_2
\vdots
L_K C_K
  • 1 行目には、交差点の数を表す N 、道路の数を表す M 、料金所の数を表す K が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目では、道路の情報が M 行で与えられる。
  • 1 + i 行目では、 i 番目の道路が結ぶ 2 つの交差点 U_i , V_i と、その道路の所要時間 W_i がスペース区切りで与えられる。道路は双方向に通行可能である。
  • M + 2 行目から M + K + 1 行目では、料金所の情報が K 行で与えられる。
  • M + 1 + j 行目では、 j 番目の料金所が設置されている交差点 L_j と、その通行料 C_j がスペース区切りで与えられる。
  • K = 0 の場合、この部分は存在しない。

出力

高橋君が交差点 1 から交差点 N まで移動するときの総コストの最小値を 1 行で出力せよ。

入力例 1

4 4 1
1 2 2
2 3 2
3 4 2
1 4 10
3 5

出力例 1

10

入力例 2

6 7 3
1 2 3
1 3 5
2 4 4
3 4 1
4 5 2
5 6 3
2 5 10
2 6
4 3
5 1

出力例 2

15

入力例 3

8 10 4
1 2 5
1 3 3
2 4 2
3 5 4
4 6 6
5 6 2
6 7 3
7 8 4
5 7 8
1 4 10
1 2
5 3
6 1
8 4

出力例 3

26

Score : 400 pts

Problem Statement

Takahashi is strolling through the streets of a city. The city has N intersections, and the intersections are connected by bidirectional roads. There are M roads in total, and each road has a required travel time. Multiple roads may connect the same pair of intersections, but there are no roads connecting an intersection to itself (no self-loops).

The city has K toll gates, each installed at a distinct intersection. The j-th toll gate is installed at intersection L_j, and its toll fee is C_j. No toll fee is charged at intersections without a toll gate.

Takahashi wants to travel from intersection 1 to intersection N. He moves from intersection to intersection via roads, and he may pass through the same intersection or the same road multiple times.

Takahashi's route is represented as a sequence of intersections v_0, v_1, v_2, \ldots, v_s (where v_0 = 1 and v_s = N). Here, each pair of consecutive intersections v_{k-1} and v_k (1 \leq k \leq s) must be directly connected by a road.

The total cost of the trip is the sum of the following two components:

  • The total travel time of the roads traversed. That is, the sum of the travel times of the roads chosen to connect v_{k-1} and v_k for k = 1, 2, \ldots, s. If the same road is traversed multiple times, it is counted that many times.
  • The total toll fees at toll gates located at intersections along the route. That is, for each intersection in v_0, v_1, \ldots, v_s, if that intersection has a toll gate, its toll fee is added. If the same intersection appears multiple times in the route, the fee is charged each time. Both the starting point (intersection 1) and the destination (intersection N) are included.

Find the minimum total cost for Takahashi to travel from intersection 1 to intersection N. It is guaranteed that intersection N is reachable from intersection 1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq N
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
  • 1 \leq L_j \leq N (1 \leq j \leq K)
  • All L_j are distinct (1 \leq j \leq K)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq K)
  • Intersection N is reachable from intersection 1
  • All input values are integers

Input

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
L_1 C_1
L_2 C_2
\vdots
L_K C_K
  • The first line contains N (the number of intersections), M (the number of roads), and K (the number of toll gates), separated by spaces.
  • From the 2nd line to the (M + 1)-th line, road information is given over M lines.
  • The (1 + i)-th line gives the two intersections U_i, V_i connected by the i-th road and its travel time W_i, separated by spaces. The road is bidirectionally traversable.
  • From the (M + 2)-th line to the (M + K + 1)-th line, toll gate information is given over K lines.
  • The (M + 1 + j)-th line gives the intersection L_j where the j-th toll gate is installed and its toll fee C_j, separated by spaces.
  • If K = 0, this part does not exist.

Output

Print the minimum total cost for Takahashi to travel from intersection 1 to intersection N in a single line.

Sample Input 1

4 4 1
1 2 2
2 3 2
3 4 2
1 4 10
3 5

Sample Output 1

10

Sample Input 2

6 7 3
1 2 3
1 3 5
2 4 4
3 4 1
4 5 2
5 6 3
2 5 10
2 6
4 3
5 1

Sample Output 2

15

Sample Input 3

8 10 4
1 2 5
1 3 3
2 4 2
3 5 4
4 6 6
5 6 2
6 7 3
7 8 4
5 7 8
1 4 10
1 2
5 3
6 1
8 4

Sample Output 3

26