← 返回题目
题库练习 假期计划
← 上一题 下一题 →

A2216 | 假期计划

来源USACO / 2013
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有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，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。


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

输入格式

* 第 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 次行程

输出格式

* 第 1 行：可能有有效路线的行程数（Q 以外）。

* 线路 2：所有可能有效路线的行程中，最低可能路线成本的总和。

输入输出样例

输入 #1
3 3 1 3 
3 1 10 
1 3 10 
1 2 7 
3 2 
2 3 
1 2
输出 #1
2 
24
C++ 编辑器
输入
输出