zoj1952 poj2263

Heavy Cargo

Time Limit: 2 Seconds Memory Limit: 65536 KB

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

#include <cstdio>
#include <cstring>
#define MAXCITIES 256
#define INF 1000000000
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

int kase = 0;    //测试数据的序号
int n, r;    //城市的个数和道路的个数
int w[MAXCITIES][MAXCITIES];    //floyd算法中的A矩阵
char city[MAXCITIES][30];    //城市名
char start[30], dest[30];    //起点城市和终点城市
int numcities;    //城市名在city数组中的序号

//把陆续读进来的城市名存储到city数组中，index函数的功能是给定一个城市名，
//返回它在city数组中的下标，如果不存在，则把该城市名追加到city数组中
int index( char* s )
{
    int i;
    for( i=0; i<numcities; i++ )
    {
        if( !strcmp(city[i],s) )  return i;
    }
    strcpy( city[i], s );
    numcities++;
    return i;
}

int read_case( )    //读入测试数据
{
    int i, j, k, limit;
    
    scanf( "%d%d", &n, &r );
    if( n==0 )  return 0;
    
    for( i=0; i<n; i++ )    //初始化邻接矩阵
    {
        for( j=0; j<n; j++ )  w[i][j] = 0;
    }
    for( i=0; i<n; i++ )  w[i][i] = INF;
    
    //读入道路网络
    numcities = 0;
    for( k=0; k<r; k++ )
    {
        scanf( "%s%s%d", start, dest, &limit );
        i = index(start);  j = index(dest);
        w[i][j] = w[j][i] = limit;    //Floyd算法中矩阵A的初始值就是邻接矩阵
    }
    
    //读入起点城市和终点城市
    scanf( "%s%s", start, dest);
    return 1;
}

void solve_case( )
{
    int i,j,k;
    for( k=0; k<n; k++ )    //Floyd-Warshall算法
    {
        for( i=0; i<n; i++ )
        {
            for( j=0; j<n; j++ )
                w[i][j] = MAX( w[i][j], MIN( w[i][k], w[k][j] ) );
        }
    }
    i = index( start );  j = index( dest );
    printf( "Scenario #%d
", ++kase );
    printf( "%d tons

", w[i][j] );
}

int main( )
{
    while ( read_case( ) )
        solve_case( );
    return 0;
}