二叉树+迭代,地址: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;
}