← 返回题目列表

AtCoder · awc0073_d

D. 包裹递送

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥在一家快递公司工作。今天,高桥收到了 N 交货请求。

送货区域包括 M 碱基编号自 1 to 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)
  • 至多有一条道路连接任意一对基地(即所有对 (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)
  • 对于每个交付请求, T_i 可从 S_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
  • 第一行包含传递请求的数量 N,碱基数 M,以及道路数量 K,用空格分隔。
  • 如下 K 行, j第行包含两个碱基 U_j, V_j 由 j第条路,长度 那条路的 W_j ,以空格分隔。
  • 如下 N 行, i第行包含出发基地 S_i 和目的地基地 T_i 的 i第一个传送请求,以空格分隔。

输出

输出所有的最短距离之和 N 单行传递请求。


样本输入 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