分数: 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