View Code of Problem 631

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>

using namespace std;


#define Max 9999999;
int a[105][105];
int flag[105];//保存是否被访问过
int dis[105];
int n;
queue<int> q;

void innt ()
{

memset(a,0,sizeof(a));
memset(flag,0,sizeof(flag));
dis[0]=0;
int i;
for(i=1;i<n;i++)
dis [i]=Max;
return ;
}

void SPFA ()
{
 q.push(0);

 while(!q.empty())
 {

 int x=q.front();
 flag[x]=1;
 int i;
 for(i=0;i<n;i++)
    {
       if(a[i][x]!=0&&(dis[x]+a[i][x])<dis[i])
       {
       dis[i]=dis[x]+a[i][x];
       if(!flag[i])
       {
       q.push(i);
       flag[i]=1;
       }
       }

    }

 q.pop();
 flag[x]=0;

 }
 return ;
}

int  change(char*s)
{
 int x=strlen(s);
 int i;
 int ans=0;
 for(i=0;i<x;i++)
 {
  ans=ans*10+(s[i]-'0');
 }
 return ans;



}
int main ()
{
//freopen("/home/ginray/text","r",stdin);
 while(scanf("%d",&n)!= EOF)
 {
 int i,j;
 innt();
 char ff[20];
 for(i=1;i<n;i++)
 {
     for(j=0;j<i;j++)
     {
       scanf("%s",&ff);
       if(strcmp(ff,"x")!=0)
       {
       int wtf=change(ff);
        a[i][j]=wtf;
        a[j][i]=wtf;
       }
     }
 }

 SPFA ();
int minn=-1*Max;
 for(i=1;i<n;i++)
 {
 if(dis[i]>minn)
   minn=dis[i];

 }

 printf("%d\n",minn);


 }
return 0;

}