Submission #1275800

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD=1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int t;cin>>t;
  for(int i=0;i<t;i++){
      int n;cin>>n;
      VVI v(n,vector<int>(n));
      bool flag=true;
      int dis[n][n];
      for(int j=0;j<n;j++){
          for(int k=0;k<n;k++){
              dis[j][k]=INF;
              if(j==k)dis[j][k]=0;
              cin>>v[j][k];
              if(v[j][k]==-1) continue;
              dis[j][k]=min(dis[j][k],v[j][k]);
          }
      }
      for(int k=0;k<n;k++){
          for(int l=0;l<n;l++){
              for(int m=0;m<n;m++){
                  if(v[l][m]!=-1&&v[l][m]>dis[l][k]+dis[k][m]) flag=false;
              }
          }
      }
      if(flag) cout<<"YES"<<endl;
      else cout<<"NO"<<endl;
  }
}

Submission Info

Judge Result