很简单,就是Floyd跑一遍双源最短路。然后输出结果最大值就行。注意一个函数atoi,可以将字符串转换成数字。
code:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int g[110][110],dis[110][110];
int main()
{
int n;
memset(g,0,sizeof(g));
cin>>n;
for(int i = 2;i <= n;i++)
{
for(int j = 1;j < i;j++)
{
char w[20];
scanf("%s",w);
if(w[0]=='x')g[i][j] = g[j][i] =0x3f3f3f3f;
else
g[i][j] = g[j][i] = atoi(w);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dis[i][j] =dis[j][i] = g[i][j];
}
}
for(int k = 1;k <= n;k++)
{
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
}
}
int ans = 0;
for(int i=1;i<=n;i++)
ans = max(ans,dis[1][i]);
cout<<ans<<endl;
}