Problem p03600 (python)

Fixed submission:
import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    cost2=deepcopy(a)
    f=np.sum(cost<a)
    if f:
        print(-1)
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print(np.sum(a[filt])//2)

if __name__=='__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from copy import deepcopy
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

from collections import defaultdict
from heapq import heapify,heappop,heappush

class Graph():
    def __init__(self, vertices, edges, weighted=True, directed=False):
        self.vertices=vertices
        self.directed=directed
        self.edges=[]
        if weighted:
            self.weights=defaultdict(lambda:0)
        self.neiborhoods=defaultdict(list)
        for edge in edges:
            self.edges.append((edge[0],edge[1]))
            self.neiborhoods[edge[0]].append(edge[1])
            self.neiborhoods[edge[1]].append(edge[0])
            if weighted:
                self.weights[(edge[0],edge[1])]=edge[2]
                if not directed:
                    self.weights[(edge[1],edge[0])]=edge[2]
    
    def dijkstra(self,vertex):
        for x in iter(self.weights.values()):
            if x<0:
                return None
        inf=float('inf')
        n=len(self.vertices)
        cost=[inf]*(n)
        cost[vertex]=0
        hq=[(self.weights[(vertex,vertex)],vertex)]
        heapify(hq)
        while hq:
            cvw=heappop(hq)
            if cvw[0]>cost[cvw[1]]:
                continue
            for w in self.neiborhoods[cvw[1]]:
                cand=cvw[0]+self.weights[(cvw[1],w)]
                if cost[w]>cand:
                    cost[w]=cand
                    heappush(hq,(cand,w))
        return cost

def main():
    n=int(readline())
    a=[list(map(int,l.split())) for l in read().splitlines()]
    v=list(range(n))
    e=[(i,j,a[i][j]) for i in range(n) for j in range(i+1,n)]
    g=Graph(v,e)
    #for k in range(n):
    #    for i in range(n):
    #        for j in range(n):
    #            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
    cost=[g.dijkstra(i) for i in v]
    s=0
    for i in range(n):
        for j in range(i,n):
            if cost[i][j]<a[i][j]:
                print(-1)
                return None
            p=[cost[i][k]+cost[k][j]-cost[i][j] for k in range(n) if k!=i and k!=j]
            if min(p)>0:
                s+=a[i][j]
    print(s)

if __name__=='__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from copy import deepcopy
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,l.split())) for l in read().splitlines()]
    cost=deepcopy(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
    s=0
    for i in range(n):
        for j in range(i+1,n):
            if cost[i][j]<a[i][j]:
                print(-1)
                return None
            detour=min([cost[i][k]+cost[k][j] for k in range(n) if k!=i and k!=j])
            if detour>cost[i][j]:
                s+=a[i][j]
    print(s)

if __name__=='__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
import deepcopy from copy
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,lst)) for lst in read().splitlines()]
    cost=deepcopy(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
    s=0
    for i in range(i):
        for j in range(i+1,n)
        if cost[i][j]<a[i][j]:
            print(-1)
            return None
        detour=min([cost[i][k]+cost[k][j] for k in range(n) if k!=i and k!=i])
        if detour>cost[i][j]:
            s+=a[i][j]
    print(s)

if __name__=='__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    wts=dict(((i,j),a[i][j]) for i in range(n) for j in range(n))
    cost=defaultdict(int)
    cost.update(wts)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[(i,j)]=min(cost[(i,j)],cost[(i,k)]+cost[(k,j)])
    edges=[e for e in wts.keys() if e[0]<e[1]]
    edges.sort(key=wts.get,reverse=True)
    s=0
    for e in edges:
        if cost[e]<wts[e]:
            print(-1)
            return None
        detour=min([cost[(e[0],i)]+cost[(i,e[1])] for i in range(n) if i!=e[0] and i!=e[1]])
        if detour>cost[e]:
            s+=wts[e]
    print(s)

if __name__=='__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    wts=dict(((i,j),a[i][j]) for i in range(n) for j in range(n))
    cost=defaultdict(int)
    cost.update(wts)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[(i,j)]=min(cost[(i,j)],cost[(i,k)]+cost[(k,j)])
    edges=[e for e in wts.keys() if e[0]<e[1]]
    edges.sort(key=wts.get,reverse=True)
    s=0
    for e in edges:
        if cost[e]<wts[e]:
            print(-1)
            return None
        detour=min([cost[(e[0],i)]+cost[(i,e[1])] for i in range(n) if i!=e[0] and i!=e[1]])
        if detour>cost[e]:
            s+=wts[e]
    print(s)

if __name__=='__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    wts=dict(((i,j),a[i][j]) for i in range(n) for j in range(n))
    cost=defaultdict(int)
    cost.update(wts)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[(i,j)]=min(cost[(i,j)],cost[(i,k)]+cost[(k,j)])
    edges=[e for e in wts.keys() if e[0]<e[1]]
    edges.sort(key=wts.get,reverse=True)
    s=0
    for e in edges:
        if cost[e]<wts[e]:
            print(-1)
            return None
        detour=min([cost[(e[0],i)]+cost[(i,e[1])] for i in range(n) if i!=e[0] and i!=e[1]])
        if detour>cost[e]:
            s+=wts[e]
    print(s)

if __name__=='__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    wts=dict(((i,j),a[i][j]) for i in range(n) for j in range(n))
    cost=defaultdict(int)
    cost.update(wts)
    for k in range(n):
        cost.update([((i,j),min(cost[(i,j)],cost[(i,k)]+cost[(k,j)])) \
          for i in range(n) for j in range(n)])
    edges=[e for e in wts.keys() if e[0]<e[1]]
    edges.sort(key=wts.get,reverse=True)
    s=0
    for e in edges:
        if cost[e]<wts[e]:
            print(-1)
            return None
        detour=min([cost[(e[0],i)]+cost[(i,e[1])] for i in range(n) if i!=e[0] and i!=e[1]])
        if detour>cost[e]:
            s+=wts[e]
    print(s)

if __name__=='__main__':
    main()