Submission #2048852

---

Source Code Expand

#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int Q, N, a[33][33];
int main() {
	cin >> Q;
	while (Q--) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> a[i][j];
			}
		}
		bool flag = true;
		for (int i = 0; i < N; i++) {
			if (a[i][i] != 0) flag = false;
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) {
					if (a[i][k] == -1 || a[k][j] == -1) continue;
					if (a[i][j] == -1 || a[i][j] > a[i][k] + a[k][j]) flag = false;
				}
			}
		}
		cout << (flag ? "YES" : "NO") << endl;
	}
	return 0;
}

Submission Info

Judge Result