26 lines
506 B
Python
26 lines
506 B
Python
import sys
|
|
|
|
input_data = sys.stdin.read().split()
|
|
N = int(input_data[0])
|
|
edges = []
|
|
idx = 1
|
|
for i in range(N):
|
|
for j in range(N):
|
|
w = int(input_data[idx])
|
|
idx += 1
|
|
if w != 100000:
|
|
edges.append((i, j, w))
|
|
d = [0] * N
|
|
for _ in range(N - 1):
|
|
for u, v, w in edges:
|
|
if d[u] + w < d[v]:
|
|
d[v] = d[u] + w
|
|
flag = False
|
|
for u, v, w in edges:
|
|
if d[u] + w < d[v]:
|
|
flag = True
|
|
break
|
|
if flag:
|
|
print("YES")
|
|
else:
|
|
print("NO")
|