二叉树+迭代，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=2263

#include <stdio.h>
#include <string.h>

const int MAX  = 0x7fffffff;

struct
{
    char str[35];
    int num;
    int lson, rson;
}tree[500];
int next;
int number;

void initin ()
{
    
    number = 0;
    next = 1;
    tree[0].str[0] = 0;
    tree[0].lson = tree[0].rson = -1;
}

int sear ( char * str )
{
    
    int p = 0;
    int value;
    
    while ( p != -1 )
    {
        value = strcmp ( str, tree[p].str );
        if ( value < 0 )
        {
            p = tree[p].lson;
        }
        else if ( value > 0 )
        {
            p = tree[p].rson;
        }
        else
        {
            return tree[p].num; 
        }
    }
    return -1;
}

int ins ( char *str )
{
    
    int p = 0;
    int value;
    
    while ( p != -1 )
    {
        value = strcmp ( str, tree[p].str );
        if ( value < 0 )
        {
            if ( tree[p].lson < 0 )
            {
                tree[p].lson = next ++;
                tree[ tree[p].lson ].num = number ++; 
                strcpy ( tree[ tree[p].lson ].str, str );
                tree[ tree[p].lson ].lson = tree[ tree[p].lson ].rson = -1;
                return tree[ tree[p].lson ].num;
            }
            p = tree[p].lson;
        }
        else
        {
            if ( tree[p].rson < 0 )
            {
                tree[p].rson = next ++;
                tree[ tree[p].rson ].num = number ++; 
                strcpy ( tree[ tree[p].rson ].str, str );
                tree[ tree[p].rson ].lson = tree[ tree[p].rson ].rson = -1;
                return tree[ tree[p].rson ].num;
            }
            p = tree[p].rson;
        }
    }
    return -1;
}

int map [201][201];

void initm ( int n )
{
    
    for ( int i=0; i<n; i++ )
    {
        for ( int j=0; j<n; j++ )
        {
            map[i][j] = MAX;
        }
    }
}

int cost[201];

int minest ( int a, int b )
{
    
    return a < b ? a : b;
}

int ford ( int s, int t, int n )
{
    
    int v, u;
    int flag = 1;
    
    for ( v=0; v<n; v++ )
    {
        cost[v] = map[s][v];
    }
    
    while ( flag )
    {
        flag = 0;
        for ( v=0; v<n; v++ )
        {
            for ( u=0; u<n; u++ )
            {
                if ( map[u][v] < MAX && cost[u] < MAX )
                {
                    int min = minest ( map[u][v], cost[u] );
                    if ( cost[v] < min || cost[v] == MAX )
                    {
                        cost[v] = min;
                        flag = 1;
                    }
                }
            }
        }
    }

    return cost[t];
}

int main ()
{
    
    int n, r;
    char c1[35], c2[35];
    int len;
    int a, b;
    int count = 0;
    
    while ( scanf ( "%d%d", &n, &r ) != EOF && ( n || r ) )
    {
        initin ();
        initm ( n );
        for ( int i=0; i<r; i++ )
        {
            scanf ( "%s%s%d", &c1, &c2, &len );
            if ( ( a = sear ( c1 ) ) < 0 )
            {
                a = ins ( c1 );
            }
            if ( ( b = sear ( c2 ) ) < 0 )
            {
                b = ins ( c2 );
            }
            map[a][b] = map[b][a] = len;
        }
        scanf ( "%s%s", &c1, &c2 );
        a = sear ( c1 );
        b = sear ( c2 );
            
        printf ( "Scenario #%d\n%d tons\n\n", ++count, ford ( a, b, n ) );
    }
    return 0;
}