BZPRO
#4093. [Usaco2013 Dec]Vacation Planning
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
Bovinia设计了连接N (1 < = N < = 20,000)个农场的航班。对于任何航班，指定了其中的k个农场作为枢纽。 (1 < = K <= 200 , K < = N)。
目前，共有M种单向航班（ 1 < = M < = 20,000 ），第i个航班从农场u_i至农场v_i花费d_i ( 1 < = d_i < =10,000 )美元。航班保证u_i或者v_i至少有一个是枢纽，任意两个农场至多只有一个航班，保证u_i≠v_i。
Bessie负责票务服务。共收到Q个度假请求，(1 < = Q < = 50,000)，其中第i个请求是从农场a_i至农场b_i 。请帮助她计算，每个请求是否满足 ，并计算：能满足的度假请求的最小费用总和。
输入格式
第1行：四个整数N,M,K,Q
第2 - M+1行：三个整数ui,vi,di
第M+2 - M+K+1行：枢纽的农场编号X (0<=X<=N)
第M+K+2..M+K+Q+1：两个整数，度假请求ai,bi
输出格式
第1行：能够满足的度假请求数
第2行：能满足的度假请求的最小费用总和
样例
样例输入
3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1
样例输出
1
20
【样例解释】
第1个请求，航线设计为1->2->3,费用为20
第2个请求，无法满足
数据范围与提示
BZPRO