Submission #1275799

---

Source Code Expand

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

int main() {
    int T;
    cin >> T;
    while(T--) {
        int N;
        cin >> N;
        vector<vector<int>> d(N, vector<int>(N));
        for(int i=0; i<N; ++i) {
            for(int j=0; j<N; ++j) {
                cin >> d[i][j];
            }
        }
        bool ok = true;
        for(int i=0; i<N; ++i) {
            ok &= d[i][i] == 0;
            for(int j=0; j<N; ++j) {
                int min_d = 1e9;
                for(int k=0; k<N; ++k) {
                    if(d[i][k] == -1 || d[k][j] == -1) {
                        continue;
                    }
                    min_d = min(min_d, d[i][k] + d[k][j]);
                }
                ok &= min_d == 1e9 && d[i][j] == -1 || min_d == d[i][j];
            }
        }
        if(ok) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

Submission Info

Judge Result