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      2017.09.28 23:54

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来求解最大生成树问题)

uva 544 - Heavy Cargo（生成树）

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

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

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