A2216. 假期计划
编程题
普及/提高-
知识点
题目描述
有N(1 <= N <= 200)个农场，用1..N编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场1..K中的农场作为枢纽(1 <= K <= 100, K <= N)。
当前共有M (1 <= M <= 10,000)条单向航线连接这些农场，从农场u\_i 到农场 v\_i, 将花费 d\_i美元。(1 <= d\_i <= 1,000,000).
航空公司最近收到Q (1 <= Q <= 10,000)个单向航行请求。第i个航行请求是从农场a\_i到农场 b\_i，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。
请计算可行航行请求的数量，及完成所有可行请求的总费用。
当前共有M (1 <= M <= 10,000)条单向航线连接这些农场，从农场u\_i 到农场 v\_i, 将花费 d\_i美元。(1 <= d\_i <= 1,000,000).
航空公司最近收到Q (1 <= Q <= 10,000)个单向航行请求。第i个航行请求是从农场a\_i到农场 b\_i，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。
请计算可行航行请求的数量，及完成所有可行请求的总费用。
输入格式
* 第 1 行：四个整数：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 次行程
* 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 次行程
输出格式
* 第 1 行：可能有有效路线的行程数（Q 以外）。
* 线路 2：所有可能有效路线的行程中，最低可能路线成本的总和。
* 线路 2：所有可能有效路线的行程中，最低可能路线成本的总和。
输入输出样例
输入 #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。
从 3 到 >2 的旅行只有一条可能的路线，费用为 10+7。从 2 号到 >3 号的行程没有有效的路线，因为没有航班离开农场 2。从 1 到 >2 的行程再次只有一条有效路线，费用为 7。