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