Problem p03837 (python)

Fixed submission:
import sys
sys.setrecursionlimit(1000001)

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(n):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000001)

def main():
    n, m = map(int, input().rstrip().split())
    dist = [[500000 for i in range(n)]for j in range(n)]

    for i in range(n):
        for j in range(n):
            if (i==j):
                dist[i][j]=0

    a = [None] * (m-1)
    b = [None] * (m-1)
    c = [None] * (m-1)

    for i in range(m):
        x, y, z = map(int, input().rstrip().split())
        dist[x-1][y-1] =  min(dist[x-1][y-1], z)
        dist[y-1][x-1] =  min(dist[x-1][y-1], z)
        a[i] = x - 1
        b[i] = y - 1
        c[i] = z
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
    #print(dist)
    result = m

    for i in range(m):
        for j in range(n):
            if dist[j][a[i]] + c[i] == dist[j][b[i]]:
                result -= 1
                break

    print(result)
    
if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000001)

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000001)

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            print(j, a[i],b[i], c[i], i, dist[j][a[i]] ,dist[j][b[i]])
            result -= 1

print(result)

Buggy submission (verdict: Runtime Error):
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Buggy submission (verdict: Runtime Error):
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Buggy submission (verdict: Runtime Error):
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Buggy submission (verdict: Runtime Error):
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(1, n):
    for j in range(1, n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
             result -= 1

print(result)

Buggy submission (verdict: Runtime Error):
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(1, n):
    for j in range(1, n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1

print(result)

Buggy submission (verdict: Runtime Error):
import sys

n, m = map(int, input().rstrip().split())
dist = [[float('inf') for i in range(n)]for j in range(n)]

for i in range(1, n):
    for j in range(1, n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1

print(result)

Buggy submission (verdict: Runtime Error):
import sys
import re
import heapq

n, m = map(int, input().rstrip().split())
dist = [[float('inf') for i in range(n)]for j in range(n)]

for i in range(1, n):
    for j in range(1, n):
        if (i==j):
            dist[i][j]=0

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1

print(result)

Buggy submission (verdict: Runtime Error):
import sys
import re
import heapq

n, m = map(int, input().rstrip().split())

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0
        else:
            dist[i][j]=float('inf')
        

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x][y] =  min(dist[x][y], z)
    dist[y][x] =  min(dist[x][y], z)
    a.append(x)
    b.append(y)
    c.append(z)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1

print(result)