比赛场次 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 简单对比
用户 结果 时间 内存 得分
Gravatardigital-T AWWWWWWWWW 2.490 s 62.28 MiB 10
Gravatar超级傲娇的AC酱 AETEEEEEEE 2.907 s 0.31 MiB 10
Gravatarcstdio AWWWWWWTTT 3.700 s 1.66 MiB 10
Gravatar请叫我“读者” WWWTTEEEEE 3.564 s 0.31 MiB 0
Gravatar雪狼 WWWWWWWWWW 3.808 s 140.84 MiB 0

假期旅行计划

★   输入文件:vacationgold.in   输出文件:vacationgold.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


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


【来源】

在此键入。