Vacation Planning
题目描述
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个请求,无法满足
提示
Gold
信息
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者