问题 5318 --收费站-训练套题T3T4

5318: 收费站-训练套题T3T4

时间限制: 3 Sec  内存限制: 256 MB
提交: 13  解决: 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,

可能有两条边连接着相同的城市。

提示


收费站



    【题目大意】



    给定一个无向图,求从uv,在总长不超过s的情况下,在所有经过的点中,f值的



最大值的最小值是多少。



    【解法一】



    动态规划。设b[i][j]表示从u出发,用i升汽油,到点j,在所有的交费中,最大值是



多少。



    然后按b[0]b[1]b[2]….,b[s]的顺序递推。



    程序比较简单,可以不用链表,只需用一个二维数组保存这个图。本做法应该算是一



个性价比很高的做法。



    时间复杂度为O(nns)。预计得分为60



    【解法二】



  先二分答案,把原题变成判定性问题。对于某一个值,要判断能不能做到就容易多了。



可以先将收费超过当前答案的点去掉,然后求uv的最短路。如果这个最短路不大于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算法并没有使用堆进行优化,可以得708 0分。

来源

 

[提交][状态]