uva_423(mri).cpp

#include<bits/stdc++.h>
using namespace std ;


#define M 1000
#define pii pair<int , int >
#define mp make_pair
#define pf printf
#define sf scanf
#define sf1(a ) scanf("%d",&a)
#define pb push_back
#define sf2(a, b) scanf("%d%d",&a ,&b)
#define rep(i,n) for(i = 0 ; i< n ;i++ )

vector<int > data  ;
vector<int > stk  ;
const int mx = 1005000000;

int fastscan(){
int ret, num = 0 , negetive = -1    ;
char ch ;
    //getchar();
    while(ch = getchar()){
     // pf("here");
    if(ch != ' ') break ;

    }
    if(ch == '-' ) negetive = 1 ;
    else    num = 10* num + ch -'0';
    if(ch ==  'x') {
    getchar();
    return -1 ;

    }
    while(1){
        ch =  getchar();
        if(ch ==  '\n' || ch == ' ' ) break ;
        num = 10* num + ch -'0';

    }
    if(negetive ==  1) {num *= -1 ;
   // pf("negetive %d\n",num );
    }
    return num  ;
}


int arr[M][M];

void warshall(int arr[][M] ,int num ){
   int i , j , k ;
   for(k =1 ; k <= num ;k++){
      for(i = 1 ;i<= num ;i++ ){
         for(j =  1;j<= num ; j++)
         {
            if(arr[i][k] + arr[k][j] <= arr[i][j]){
               arr[i][j] = arr[i][k] + arr[k][j] ;

          }

         }
   }
}


return ;
}



int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);

    int  n , i , j ,  k , cs= 0;
    while(scanf("%d",&n) == 1 ){
      cs++;
        rep(i , M)rep(j , M ) arr[i][j] = mx;
    getchar();

        for(i = 2;i <= n ;i++){
            for(j =  1 ; j< i ; j++ )
            {
                k = fastscan();
                if( k  == -1 ) arr[i][j] =  arr[j][i] =  mx  ;
                else arr[i][j] = arr[j][i] =  k ;

            }

        }
      warshall(arr, n);


    rep(i , n+1 ) arr[i][i] = 0;
 /* if(cs == 45)
    rep(i, n ){
      rep(j , n )
      pf("%d ",arr[i+1][j+1]);
      pf("\n");
    }
   // */

        long long sum = 0  ;
        int max = 0 ;

        for(i = 1 ; i<= n ;i++){

    //  pf("here %d\n",arr[1][i]);
            if(arr[1][i] >= max){
        max =  arr[1][i];
        //  cout << max << endl;
            }
        }
        if(max ==  mx)
      pf("0\n");
    else
        pf("%d\n", max);
    }

    return 0 ;
}