比赛场次 | 228 |
---|---|
比赛名称 | 20140307 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2014-03-07 19:00:00 |
结束时间 | 2014-03-07 22:00:00 |
开放分组 | 全部用户 |
注释介绍 | usaco 2013 12月月赛金组题 |
题目名称 | 假期旅行计划 |
---|---|
输入输出 | vacationgold.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
digital-T | AWWWWWWWWW | 2.490 s | 62.28 MiB | 10 |
超级傲娇的AC酱 | AETEEEEEEE | 2.907 s | 0.31 MiB | 10 |
cstdio | AWWWWWWTTT | 3.700 s | 1.66 MiB | 10 |
请叫我“读者” | WWWTTEEEEE | 3.564 s | 0.31 MiB | 0 |
雪狼 | WWWWWWWWWW | 3.808 s | 140.84 MiB | 0 |
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号农场没有出发的航班,那头可怜的牛只能滞留在该地。
在此键入。