Submission #1275850

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int t, n;

	cin >> t;

	for (int x = 0; x < t; x++) {
		bool flag = false;

		cin >> n;

		vector<vector<long long>> dis1(n, vector<long long>(n));
		vector<vector<long long>> dis2;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> dis1[i][j];

				if (dis1[i][j] == -1) {
					dis1[i][j] = 1000000;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			if (dis1[i][i] != 0) {
				flag = true;
			}
		}

		dis2 = dis1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					dis2[j][k] = min(dis2[j][k], dis2[j][i] + dis2[i][k]);
				}
			}
		}

		if (dis1 == dis2 && flag == false) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
}

Submission Info

Judge Result