2 shunfurh shunfurh 于 2017.09.12 19:22 提问

Heavy Cargo

Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive.
Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.

Input

The input will contain one or more test cases. The first line of each test case will contain two integers: the number of cities n (2 <= n <= 200) and the number of road segments r (1 <= r <= 19900) making up the street network.

Then r lines will follow, each one describing one road segment by naming the two cities connected by the segment and giving the weight limit for trucks that use this segment. Names are not longer than 30 characters and do not contain white-space characters. Weight limits are integers in the range 0 - 10000. Roads can always be travelled in both directions.

The last line of the test case contains two city names: start and destination.

Input will be terminated by two values of 0 for n and r.

Output

For each test case, print three lines:

a line saying "Scenario #x" where x is the number of the test case
a line saying "y tons" where y is the maximum possible load
a blank line

Sample Input

4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0

Sample Output

Scenario #1
80 tons

Scenario #2
170 tons

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.28 23:54
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
POJ 2263 Heavy Cargo(Floyd变形)
POJ 2263 Heavy Cargo(Floyd变形) http://poj.org/problem?id=2263 题意:给你一个无向图,图中每条路有一个负重限制v.现在要你求从A点到B的的所有可能路径中,负重量最大的那个值.即假设从A到B有一条路径,该路径包括负重为10,20,30,5的4条路.那么该路径的负重就是5.现在我们要求一条负重值最大的路. 分析:        此题可由
(Relax dijkstra1.2)POJ 2263 Heavy Cargo(使用dijkstra来求解最大生成树问题)
题意:有n个城市,m条连接两个城市的道路,每条道路有自己的最大复载量。现在问从城市a到城市b,车上的最大载重能为多少。   思路:dijkstra。在松弛的地方要改一下,即当前点now的最大负载为min(dict[now], edge[now][i]),这很关键。其次输入求城市名称对应的顶点编号要注意下,然后就是赤裸裸的dij了。 #include #include
uva 544 - Heavy Cargo(生成树)
题目链接:uva 544 - Heavy Cargo #include #include #include #include #include #include using namespace std; const int maxn = 205; const int maxm = 20005; struct Edge { int u, v, d; bool opera
POJ2263:Heavy Cargo
http://poj.org/problem?id=2263 题目是求一条能承载最重货物量的路径,只需求出最大的承载量。这题可以利用Floyd思想来解决,从i到j的路径中假设经过k,则该条路最少的承载量为min{ map[i][k] , map[k][j]},故对应的i到j的最大承载量为max{ map[i][j] , min{map[i][k] , map[k][i]}}。这样问题就可以解决了
floyd UVA544 Heavy Cargo
题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19666 题意:从一个点到另一个点,每条路径上边最小值,所有路径的这个最小值的最大值 思路:floyd,gmin后gmax。顺便学习了下map,把string做数组下标进行调用。查询某个键是否存在有两种方法,第一是map.count(key),第二是先map.cl
poj_2263 Heavy Cargo (Dijkstra)
Heavy Cargo Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2264 Accepted: 1252 题目链接:http://poj.org/problem?id=2263 Description Big Johnsson Truck
Heavy Cargo 最短路变种
/*就是求所有边中最小边的最大值。 相对应的就是求所有边中最大边的最小值,就是frogger。 该题的转移方程就是:dist[j]=max(dist[j],min(dist[k],map[k][j]));*/ #include #include #include #include #include #define inf 99999999 using namespace std; int
POJ 2263 Heavy Cargo
这种是通行能力(可称容量)最大路,此种路称为最大容量路。 设城市i到城市j的承重载量w[i,j],则初始时从K到M没有直接路径,w[i, j] = 0; 假如中间点H后,K到M的载重量修改为:w[K, M] = MAX{w[K, M], MIN(w[W][H]), w[H][M] };   所以floyd要修改为: A(-1)[i][j] = Edge[i][j]; A(k)[i][j
Heavy Cargo(数论)
Description Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is ne
UVa 544 - Heavy Cargo
题目:有一个载重无限的卡车运输货物,在城市中每条道路有一个能承受的最大重量,             现在从一个城市到另一个城市运送货物,问最大的运输重量。 分析:图论,最短路,最小生成树。找一条从起点到终点的路径,使得其中最窄的路段最宽。             从起点开始不断向周围扩散,像dijstra算法和prime算法一样,只是维护最大值即可。 说明:道路是双向的,重复的路径认为是