OI题库

【题目描述】

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号农场没有出发的航班，那头可怜的牛只能滞留在该地。

【来源】

在此键入。