输出格式有坑
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
//#include <malloc.h>
using namespace std;
int map[105][105],ans[105],flag[105];char st[15];
int main()
{
int i,j,k,n,len,x,min,temp,t;
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
scanf("%s",st);
len=strlen(st);
x=0;
if(st[0]=='x')
{
map[i][j]=9999999;map[j][i]=9999999;
continue;
}
for(k=0;k<len;k++)
{
x*=10;x+=st[k]-'0';
}
map[i][j]=x;map[j][i]=x;
}
}
for(i=1;i<=n;i++)
{
ans[i]=map[1][i];
}
memset(flag,0,sizeof flag);
flag[1]=1;
for(i=1;i<=n;i++)
{
min=9999999;
for(j=2;j<=n;j++)
{
if(ans[j]<min&&flag[j]==0)
{
min=ans[j];
temp=j;
}
}
flag[temp]=1;
for(j=1;j<=n;j++)
{
if(ans[temp]+map[temp][j]<ans[j])
ans[j]=ans[temp]+map[temp][j];
}
}
int max=0;
for(j=2;j<=n;j++)
{
if(max<ans[j])
max=ans[j];
}
if(t!=0)
printf("%d\n\n",max);
else printf("%d\n",max);
}
}
return 0;
}
监心司
发布了45 篇原创文章 · 获赞 1 · 访问量 3537
私信
关注