假期旅行计划

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file vacationgold.in Output file vacationgold.out

【题目描述】


Bovinia航空公司专门为N(1<=N<=20,000)个有牛居住的农场提供航空服务,跟其它航空公司一样,它们将其中的K(1<=K<=200,K<=N)个农场设成了航运枢纽。

目前,Bovinia航空公司提供了M(1<=M<=20,000)条单向航班,其中第i个航班从农场u_i出发至农场v_i,费用为d_i(1<=d_i<=10,000)美元。正像其它规划合理的航空公司一样,每一条航线的u_i和v_i中至少有一个为航运枢纽,在任意两个农场的任意方向上都最多只有一个直达航班,且任意一个航班的起点与始点都不会是同一个农场。

Bessie负责航空公司的票务工作。不幸的是,由于她花了几个小时外出吃了顿美味大餐,回来时便发现有Q(1<=Q<=50,000)个购票需求等着她处理,其中第i个需求是要从农场a_i到农场b_i。

处理这些票务快要把Bessie累垮了,请你帮她计算一下是否每个购票需求都能得到满足,以及能够满足的购票需求总计的费用最少是多少?

为了缩减输出规模,你只需输出能够被满足的购票需求的个数,和这些需求总共所需的最小费用。注意:这个费用有可能超出32位整型所能表示的范围。



【输入格式】


第1行有4个整数:N,M,K,Q;

接下来有M行,其中的第i行分别为u_i,v_i,d_i,(1<=u_i,v_i<=N,u_i!=v_i);

再接下来有K行,每行一个整数,为一个航运枢纽的编号(编号均在1~N之间);

最后有Q行,每行有两个数,表示一个购票需求中的起点和终点(1<=a_i,b_i<=N,a_i!=b_i)。


【输出格式】


第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;因为从3号农场没有出发的航班,那头可怜的牛只能滞留在该地。


【来源】

在此键入。