Submission #533439

---

Source Code Expand

#!/usr/bin/env python
# -*- coding: utf-8 -*-

T = int(input())
for t in range(T):
    N = int(input())
    G = [[float("inf") for i in range(N)] for j in range(N)]
    dist = [[float("inf") for i in range(N)] for j in range(N)]

    for i in range(N):
        for j,c in enumerate(map(int,input().split())):
            G[i][j] = c if c >= 0 else float("inf")

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], G[i][k] + G[k][j])
    for i in range(N):
        if dist[i] != G[i]:
            break
    else:
        print("YES")
        continue
    print("NO")

Submission Info

Judge Result