[Usaco2013 Dec]Vacation Planning

时间限制:10s      空间限制:128MB

题目描述

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

Menuappsclose