import sys import numpy as np from collections import defaultdict from

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
import sys
import numpy as np
from collections import defaultdict
from itertools import izip
from StringIO import StringIO
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance
def dijsktra(graph, initial):
visited = {initial: 0}
path = {}
nodes = set(graph.nodes)
while nodes:
min_node = None
for node in nodes:
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node
if min_node is None:
break
nodes.remove(min_node)
current_weight = visited[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited
a = sys.stdin.readlines()
size, mtx = int(a[0]), a[1:]
if size == 1:
if int(mtx[0][0]) == 0:
print 'YES'
else:
print 'NO'
exit()
mtx = '\n'.join(mtx)
mtx = np.loadtxt(StringIO(mtx))
for i, j in izip(xrange(len(mtx)), xrange(len(mtx))):
if mtx[i, i] != 0:
print 'NO'
exit()
for i in xrange(len(mtx)):
for j in xrange(len(mtx)):
if i != j and mtx[i, j] == 0:
print 'NO'
exit()
for i in xrange(len(mtx)):
for j in xrange(len(mtx)):
if i < j:
if mtx[i, j] != mtx[j, i]:
print 'NO'
exit()
G = Graph()
for i, row in enumerate(mtx):
G.add_node(i)
if i == 0:
continue
min_idx = row[:i].argmin()
G.add_edge(i, min_idx, row[min_idx])
for i in xrange(len(mtx)):
p = dijsktra(G, i)
for j in xrange(len(mtx)):
if j in p and p[j] != mtx[i][j]:
print 'NO'
exit()
print 'YES'