You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $N$（$1 \leq N \leq 200$）个农场，用 $1$ 到 $N$ 编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场 $1$ 到 $K$ 中的农场作为枢纽（$1 \leq K \leq 100$，$K \leq N$）。

当前共有 $M$（$1 \leq M \leq 10000$）条单向航线连接这些农场，从农场 $u_i$ 到农场 $v_i$，将花费 $d_i$ 美元（$1 \leq d_i \leq 1000000$）。

航空公司最近收到 $Q$（$1 \leq Q \leq 10000$）个单向航行请求。第 $i$ 个航行请求是从农场 $a_i$ 到农场 $b_i$，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。

请计算可行航行请求的数量，及完成所有可行请求的总费用。

输入格式

• 第一行：四个整数：$N$、$M$、$K$ 和 $Q$。
• 第 2 行到第 $1 + M$ 行：第 $i + 1$ 行包含第 $i$ 次飞行的 $u_i$、$v_i$ 和 $d_i$。
• 第 $2 + M$ 行到第 $1 + M + Q$ 行：第 $1 + M + i$ 行根据 $a_i$ 和 $b_i$ 描述第 $i$ 次行程。

输出格式

• 第一行：在 $Q$ 次行程中，存在可行路线的行程数量。
• 第二行：在所有存在可行路线的行程中，这些行程的最小可能路线成本之和。

输入输出样例

输入 #1

3 3 1 3 
3 1 10 
1 3 10 
1 2 7 
3 2 
2 3 
1 2

输出 #1

2 
24

说明/提示

有三个农场（编号为 1 到 3）；农场 1 是一个枢纽。有一趟从农场 3 到农场 1 费用为 10 美元的航班，以此类推。我们希望寻找从农场 3 到农场 2、从农场 2 到农场 3 以及从农场 1 到农场 2 的行程路线。

从农场 3 到农场 2 的行程只有一条可能的路线，费用为 10 加上 7（美元）。从农场 2 到农场 3 的行程没有有效的路线，因为没有从农场 2 出发的航班。从农场 1 到农场 2 的行程同样只有一条有效的路线，费用为 7（美元）。