# 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' ```