Submission #1692336

---

Source Code Expand

#include<bits/stdc++.h>
#define loop(i, a, b) for(int i = a; i < b; i++) 
#define rep(i, a) loop(i, 0, a)
using namespace std;
const int MOD = 1000000007;
const int inf = 1e9;
using vi = vector <int>;
using vvi = vector <vi>;
using vc = vector <char>;
using vvc = vector <vc>;
using vs = vector <string>;
using vvs = vector <vs>;
//g++ -std==c++14
//setprecision(10)
int main(){
    int t;
    cin >> t;
    rep(va, t){
        int n;
        cin >> n;
        vvi G(n, vi(n));
        rep(i, n)rep(j, n){
            cin >> G[i][j];
            if(G[i][j] == -1)
                G[i][j] = inf;
            if(G[i][j] && i == j){
                cout << "NO" << endl;
                goto matoba;
            }
        }
        rep(k, n)rep(i, n)rep(j, n)
            if(G[i][j] > G[i][k] + G[k][j]){
                cout << "NO" << endl;
                goto matoba;
            }
        cout << "YES" << endl;
        matoba:;
    }
}

Submission Info

Judge Result