Problem p02889 (python)

Fixed submission:
N,M,L = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())
    
Q = int(input())
qlist = [[int(q) for q in input().split()] for _ in range(Q)]

INF = 10**18
d = [[INF]*N for _ in range(N)]
for i in range(M):
    d[A[i]-1][B[i]-1] = C[i]
    d[B[i]-1][A[i]-1] = C[i]

for i in range(N):
    d[i][i] = 0
        

# Warshall-Floyd法
# DP
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

d2 = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            d2[i][j] = 0
        elif d[i][j] <= L:
            d2[i][j] = 1
            
for k in range(N):
    for i in range(N):
        for j in range(N):
            d2[i][j] = min(d2[i][j], d2[i][k]+d2[k][j])
                
for i in range(Q):
    s = qlist[i][0]-1
    t = qlist[i][1]-1
    ans = d2[s][t]
    if ans >= INF:
        print(-1)
    else:
        print(ans-1)

Buggy submission (verdict: Runtime Error):
N,M,L = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())
    
Q = int(input())
qlist = [[int(q) for q in input().split()] for _ in range(Q)]

INF = 10**13
d = [[INF]*N for _ in range(N)]
for i in range(M):
    d[A[i]-1][B[i]-1] = C[i]
    d[B[i]-1][A[i]-1] = C[i]
    d[i][i] = 0
        

# Warshall-Floyd法
# DP
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

d2 = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            d2[i][j] = 0
        elif d[i][j] <= L:
            d2[i][j] = 1
            
for i in range(N):
    for j in range(N):
        for k in range(N):
            d2[i][j] = min(d2[i][j], d2[i][k]+d2[k][j])
                
for i in range(Q):
    s = qlist[i][0]-1
    t = qlist[i][1]-1
    ans = d2[s][t]
    if ans >= INF:
        print(-1)
    else:
        print(ans-1)

Buggy submission (verdict: Runtime Error):
N,M,L = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())
    
Q = int(input())
qlist = [[int(q) for q in input().split()] for _ in range(Q)]

INF = 10**15
G = [[INF for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    if C[i] <= L:
        G[A[i]][B[i]] = C[i]
        G[B[i]][A[i]] = C[i]
        

        
def dijkstra(s,t,n,w,cost,L):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [INF] * n
    used = [False] * n
    d[s] = 0
    c = [INF]*n
    c[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and c[i] < c[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
            t = c[v]+((d[v]-c[v]*L)+cost[v+1][j+1])
            if (c[v]+((d[v]-c[v]*L)+cost[v+1][j+1]))%L == 0:
                f = t//L -1
            c[j] = min(c[j], min(c[v]+((d[v]-c[v]*L)+cost[v+1][j+1])//L,f))
            if c[j] > min(c[v]+((d[v]-c[v]*L)+cost[v+1][j+1])//L,f):
                d[j] = d[v] + cost[v+1][j+1]
            elif c[j] == min(c[v]+((d[v]-c[v]*L)+cost[v+1][j+1])//L,f):
                d[j] = min(d[j], d[v] + cost[v+1][j+1])
    print(c)
    return c[t]


for i in range(Q):
    ans = dijkstra(qlist[i][0]-1,qlist[i][1]-1,N,M,G,L)
    if ans == INF:
        print(-1)
    else:
        print(ans)