View Code of Problem 631

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

#define N 105
#define MAXN 1000000007

int n, map[N][N];
int time[N][N];

void Floyd(){
	for(int i = 1; i <= n; i++)
		for(int j = 1; j < i; j++)
			time[j][i] = time[i][j] = map[i][j];
			
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j < i; j++)
				if(time[i][j] > (time[i][k] + time[k][j]))
					time[i][j] = time[j][i] = time[i][k] + time[k][j];
} 
	
int change(char temp[]){
	if(temp[0] == 'x')
		return MAXN;
	int num = 0;
	for(int i = 0; temp[i]; i++)
		num = num * 10 + temp[i] - '0';
	return num;
}

int main(){
	memset(map, 0, sizeof(map));
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j < i; j++){
			char temp[15];
			scanf("%s", temp);
			getchar();
			map[i][j] = map[j][i] = change(temp);
		}
	Floyd();
	int max = 0;
	for(int i = 2; i < n; i++)
		if(time[1][i] > max)
			max = time[1][i];
	printf("%d\n", max);
	return 0;
}