1502.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <iostream.h>
#include <stdlib.h>

int dis[100][100];

int main()
{
	int i, j, k, n, t;
	char w[100];

	cin>>n;

	for( i=0; i<n; i++ )
	{
		dis[i][i] = 0;
		for( j=0; j<i; j++ )
		{
			cin>>w;
			if( w[0] == 'x' ) t = 999999999;
			else t = atoi( w );

			dis[i][j] = dis[j][i] = t;
		}
	}

	for( k=0; k<n; k++ )
	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		if( ( t = dis[i][k] + dis[k][j] ) < dis[i][j] )
			dis[i][j] = t;

	t = 0;
	for( i=1; i<n; i++ )
		if( dis[0][i] > t ) t = dis[0][i];

	cout<<t<<endl;

	return 0;
}