Problem p03602 (python)

Fixed submission:

N = int(input())

import numpy as np

G = np.array([list(map(int,input().split())) for i in range(N)], dtype=np.uint32)

import scipy.sparse.csgraph as csg

G2 = csg.floyd_warshall(G,directed=False)

if np.any(G != G2):
  print(-1)
else:
  G[G==0] = 2*10**9
  t = 0
  for i in range(N):
    for j in range(i+1,N):
      n = np.min(G[i]+G[j])
      if n > G[i,j]:
        t += G[i,j]


  print(t)

Buggy submission (verdict: Runtime Error):

N = int(input())

import numpy as np

G = np.array([list(map(int,input().split())) for i in range(N)])

import scipy.sparse.csgraph as csg

G2 = csg.floyd_warshall(G,directed=False)

if np.any(G != G2):
  print(-1)
else:
  G = G2
  T = csg.minimum_spanning_tree(G)
  total = np.sum(T)
  T = csg.floyd_warshall(T,directed=False,overwrite=True)

  import heapq as hq

  remaining = []
  counter = [0]*N

  indices = set()
  for i,j in zip(*np.nonzero(T!=G)):
    indices.add(i)
    counter[i] += 1
    counter[j] += 1
    if i > j:
      remaining.append((G[i,j],i,j))
  
  hq.heapify(remaining)
  while remaining:
    d,i,j = hq.heappop(remaining)
    counter[i] -= 1
    counter[j] -= 1
    if d != T[i,j]:
      T[i,j] = d
      T[j,i] = d
      total += d
      T2 = csg.dijkstra(T,directed=False,indices=list(indices))
      for i,j in enumerate(indices):
        T[j] = T2[i]
    if counter[i] == 0:
      indices.discard(i)
    if counter[j] == 0:
      indices.discard(j)
    

  print(int(total))

Buggy submission (verdict: Runtime Error):
N = int(input())
 
import numpy as np
 
G = np.array([list(map(int,input().split())) for i in range(N)])
 
import scipy.sparse.csgraph as csg
 
G2 = csg.floyd_warshall(G,directed=False)
 
if np.any(G != G2):
  print(-1)
else:
  G = G2
  T = csg.minimum_spanning_tree(G)
  total = np.sum(T)
  T = csg.floyd_warshall(T,directed=False,overwrite=True)
 
  import heapq as hq
 
  remaining = []
  delta = T!=G
 
  indices = set()
  for i,j in zip(*np.nonzero(delta)):
    indices.add(i)
    if i > j:
      remaining.append((G[i,j],i,j))
  
  hq.heapify(remaining)
  while remaining:
    d,i,j = hq.heappop(remaining)
    delta[i,j] = True
    delta[j,i] = True
    if d != T[i,j]:
      T[i,j] = d
      T[j,i] = d
      total += d
      T2 = csg.dijkstra(T,directed=False,indices=list(indices))
      for i,j in enumerate(indices):
        T[j] = T2[i]
    
    if np.all(delta[i]):
      indices.discard(i)
    if np.all(delta[j]):
      indices.discard(j)
 
  print(int(total))

Buggy submission (verdict: Runtime Error):

N = int(input())

import numpy as np

G = np.array([list(map(int,input().split())) for i in range(N)])

import scipy.sparse.csgraph as csg

G2 = csg.floyd_warshall(G,directed=False)

if np.any(G != G2):
  print(-1)
else:
  G = G2
  T = csg.minimum_spanning_tree(G)
  total = np.sum(T)
  T = csg.floyd_warshall(T,directed=False,overwrite=True)

  import heapq as hq

  remaining = []
  delta = T!=G

  indices = set()
  for i,j in zip(*np.nonzero(delta)):
    indices.add(i)
    if i > j:
      remaining.append((G[i,j],i,j))
  
  hq.heapify(remaining)
  while remaining:
    d,i,j = hq.heappop(remaining)
    delta[i,j] = True
    delta[j,i] = True
    if d != T[i,j]:
      T[i,j] = d
      T[j,i] = d
      total += d
      T2 = csg.dijkstra(T,directed=False,indices=list(indices))
      for i,j in enumerate(indices):
        T[j] = T2[i]
    
    if np.all(delta[i]):
      indices.remove(i)
    if np.all(delta[j]):
      indices.remove(j)

  print(int(total))