View Code of Problem 631

#include<stdio.h>
#include<string.h>
#define max 105
#define mmax 10005
const int maxn=100000000;
int map[max][max];
int min[max];
struct queue
{
	int deal[mmax];
	int front,rear;
}qu;
void create()
{
	qu.front=qu.rear=0;
}
int main()
{
	int n,m,i,j,k,sum,temp,ans;
	char str[20];
	scanf("%d",&n);
	for(i=2;i<=n;i++)
		for(j=1;j<i;j++)
		{
			scanf("%s",str);
			if(str[0]=='x')
				map[i][j]=map[j][i]=maxn;
			else
			{
				sum=0;
				m=strlen(str);
				for(k=0;k<m;k++)
					sum=sum*10+(str[k]-'0');
				map[i][j]=map[j][i]=sum;
			}
		}
	for(i=1;i<=n;i++)
		map[i][i]=0;
	for(i=2;i<=n;i++)
		min[i]=maxn;
	create();
	qu.deal[qu.rear++]=2;
	while(qu.front!=qu.rear)
	{
		temp=qu.deal[qu.front++];
		for(i=2;i<=n;i++)
		{
			if(map[i][temp]==maxn)
				continue;
			if(min[i]>(map[1][temp]+map[temp][i]))
			{
				qu.deal[qu.rear++]=i;
				min[i]=map[1][temp]+map[temp][i];
			}
		}
	}
	ans=min[2];
	for(i=3;i<=n;i++)
		if(min[i]>ans)
			ans=min[i];
	printf("%d\n",ans);
	return 0;
}