第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
假期旅行计划
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号农场没有出发的航班,那头可怜的牛只能滞留在该地。
【来源】
在此键入。