Submission #1275822

---

Source Code Expand

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

int main(){
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int n;
        cin>>n;
        vector<vector<int>> edge(n,vector<int>(n,-1));
        vector<vector<int>> a(n,vector<int>(n));
        const int INF=1e8;
        vector<vector<int>> dp(n,vector<int>(n,INF));
        bool isok=true;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>a[i][j];
                if(a[i][j]!=-1) dp[i][j]=a[i][j];
                if(a[i][j]!=0 && i==j) isok=false;
            }
        }
        
            for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
                }
            }
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
            if(dp[i][j]==INF && a[i][j]==-1 || a[i][j]==dp[i][j]){
                continue;
            }
            else{
                isok=false;
            }
        }
        }
        cout<<(isok ? "YES" : "NO")<<endl;
    
    }
    return 0;
}

Submission Info

Judge Result