P5158: 收费站-训练套题T3T4
传统题
3.000s
时间限制
256MB
内存限制
3 提交
2 解决
【题目描述】
4.收费站（cost.pas/c/cpp）
【问题描述】
某个国家有n个城市，编号为1，2，3，...n,这个国家修建了m条双向的公路。每条公路连接两个城市。沿着某天公路，开车从一个城市到另一个城市，需要花费一定的汽油。
开车每经过一个城市，都会被收取一定的费用（包括起点和终点城市）。所有收费站都在城市中，在城市间的公路上没有任何的收费站。
现在要开车从城市u到城市v（1<=u,v<=n）,汽车最多可以装下s升的汽油。在出发的时候，车的油箱是满的，并且在路上不能加油。
在能到达目的地的前提下，收费站交费中最多的一次最少是多少。
【输入格式】
第一行5个正整数，n,m,u,v,s
接下来n行，每行一个正整数fi，表示城市i收费站的收费
再接下来m行，每行3个正整数，ai，bi，ci（1<=ai,bi<=n）,表示城市ai和bi之间有一条公路，ci表示该公路花费的汽油量。
【输出格式】
一个整数，表示交费最多的一次的最小值。
如果无法到达目的地，输出-1.
【输入样例】
4 4 2 3 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
【输出样例】
8
【问题规模】
对于60%的数据，满足n<=200,m<=10000,s<=200
对于100%的数据，满足n<=10000,m<=50000,s<=1000000000
对于100%的数据，满足ci<=1000000000,fi<=1000000000,
可能有两条边连接着相同的城市。
【提示】
收费站
【题目大意】
给定一个无向图，求从u到v，在总长不超过s的情况下，在所有经过的点中，f值的
最大值的最小值是多少。
【解法一】
动态规划。设b[i][j]表示从u出发，用i升汽油，到点j，在所有的交费中，最大值是
多少。
然后按b[0]，b[1]，b[2]…．，b[s]的顺序递推。
程序比较简单，可以不用链表，只需用一个二维数组保存这个图。本做法应该算是一
个性价比很高的做法。
时间复杂度为O(n奉n木s)。预计得分为60。
【解法二】
先二分答案，把原题变成判定性问题。对于某一个值，要判断能不能做到就容易多了。
可以先将收费超过当前答案的点去掉，然后求u到v的最短路。如果这个最短路不大于s，说明此答案可以做到，否则不行。
二分答案的时间为O(log maxlongint)。求最短路用经过堆优化的d i j k s t r a，时间为
O(m*logn)。总时间为O(m*logn*log maxlongint)。预计得分100。
【出题人的意图】
本题考查最短路算法，但是果直接考最短路，又显得太直接，所以就饶饶弯子，需要二分答案，再求最短路。本题的编程复杂度比较高，图需用链表保存，d i jk s t ra算法需要用堆进行优化。所以笔者在做测试数据的时候，设计了6个数据较小的点，让动态规划的做法能得60分。如果选手在比赛场上，没有足够的时间做此题，或者是对二分答案、最短路算法、堆不是很熟悉，那么可以考虑写一个简单的动态规划，拿60分也是一个不错的选择。另外，如果先二分答案，但是d i j k s t ra算法并没有使用堆进行优化，可以得70～8 0分。