D - 荷物の配送 解説 /

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

配点 : 400 点

問題文

高橋君は配送会社で働いています。今日、高橋君のもとに N 件の配送依頼が届きました。

配送エリアは 1 から M までの番号がついた M 個の拠点と、それらを結ぶ K 本の双方向の道路で構成されています。 j 番目の道路 (1 \leq j \leq K) は拠点 U_j と拠点 V_j を結び、その道路の長さは W_j です。

i 番目の配送依頼 (1 \leq i \leq N) では、出発拠点 S_i から届け先拠点 T_i まで荷物を届ける必要があります。各配送依頼について、出発拠点から届け先拠点までの最短距離（通る道路の長さの合計の最小値）を求め、 N 件すべての最短距離の合計を計算してください。

なお、すべての配送依頼について、出発拠点から届け先拠点へ道路を辿って到達可能であることが保証されています。

制約

  • 1 \leq N \leq 10^5
  • 2 \leq M \leq 200
  • 1 \leq K \leq \frac{M(M-1)}{2}
  • 1 \leq U_j < V_j \leq M (1 \leq j \leq K)
  • 1 \leq W_j \leq 10^6 (1 \leq j \leq K)
  • 同じ拠点の組を結ぶ道路は高々 1 本である（すなわち、(U_j, V_j) の組はすべて異なる）
  • 1 \leq S_i \leq M (1 \leq i \leq N)
  • 1 \leq T_i \leq M (1 \leq i \leq N)
  • S_i \neq T_i (1 \leq i \leq N)
  • すべての配送依頼について、S_i から T_i へ到達可能である
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_K V_K W_K
S_1 T_1
S_2 T_2
\vdots
S_N T_N
  • 1 行目には、配送依頼の件数 N、拠点の数 M、道路の本数 K が空白区切りで与えられる。
  • 続く K 行のうち j 行目には、j 番目の道路が結ぶ 2 つの拠点 U_j, V_j と、その道路の長さ W_j が空白区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目の配送依頼の出発拠点 S_i と届け先拠点 T_i が空白区切りで与えられる。

出力

N 件の配送依頼における最短距離の合計を 1 行で出力せよ。

入力例 1

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

出力例 1

11

入力例 2

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

出力例 2

25

入力例 3

5 6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9
1 5
2 6
3 4
6 4
1 4

出力例 3

76

Score : 400 pts

Problem Statement

Takahashi works at a delivery company. Today, Takahashi received N delivery requests.

The delivery area consists of M bases numbered from 1 to M, connected by K bidirectional roads. The j-th road (1 \leq j \leq K) connects base U_j and base V_j, and has length W_j.

For the i-th delivery request (1 \leq i \leq N), a package must be delivered from the departure base S_i to the destination base T_i. For each delivery request, find the shortest distance from the departure base to the destination base (the minimum total length of roads traversed), and calculate the sum of the shortest distances for all N requests.

It is guaranteed that for every delivery request, the destination base is reachable from the departure base by following roads.

Constraints

  • 1 \leq N \leq 10^5
  • 2 \leq M \leq 200
  • 1 \leq K \leq \frac{M(M-1)}{2}
  • 1 \leq U_j < V_j \leq M (1 \leq j \leq K)
  • 1 \leq W_j \leq 10^6 (1 \leq j \leq K)
  • There is at most one road connecting any pair of bases (i.e., all pairs (U_j, V_j) are distinct)
  • 1 \leq S_i \leq M (1 \leq i \leq N)
  • 1 \leq T_i \leq M (1 \leq i \leq N)
  • S_i \neq T_i (1 \leq i \leq N)
  • For every delivery request, T_i is reachable from S_i
  • All input values are integers

Input

The input is given from standard input in the following format:

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_K V_K W_K
S_1 T_1
S_2 T_2
\vdots
S_N T_N
  • The first line contains the number of delivery requests N, the number of bases M, and the number of roads K, separated by spaces.
  • In the following K lines, the j-th line contains the two bases U_j, V_j connected by the j-th road, and the length W_j of that road, separated by spaces.
  • In the following N lines, the i-th line contains the departure base S_i and the destination base T_i of the i-th delivery request, separated by spaces.

Output

Output the sum of the shortest distances for all N delivery requests in a single line.

Sample Input 1

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

Sample Output 1

11

Sample Input 2

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

Sample Output 2

25

Sample Input 3

5 6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9
1 5
2 6
3 4
6 4
1 4

Sample Output 3

76