Submission #1982999

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int t;
  cin >> t;
  while(t--) {
    int n;
    cin >> n;
    int a[33][33];
    int b[33][33];
    rep(i, n) rep(j, n) {
      cin >> a[i][j];
      if(a[i][j] == -1) a[i][j] = inf;
      b[i][j] = a[i][j];
    }
    rep(i, n) b[i][i] = 0;
    rep(i, n) rep(j, n) rep(k, n) {
      chmin(b[j][k], b[j][i]+b[i][k]);
    }
    /*
    rep(i, n) {
      rep(j, n) cout << b[i][j] << " ";
      cout << endl;
    }
    */
    bool flag = true;
    rep(i, n) rep(j, n) {
      if(a[i][j] != b[i][j]) flag = false;
    }
    cout << (flag ? "YES" : "NO") << endl;
  }

  return 0;
}

Submission Info

Judge Result