Problem p02991 (python)

Fixed submission:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# vertexごとに3つの状態数を持つ
N, M = lr()
graph = [[] for _ in range((N+1)*3)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for i in graph[prev]:
            #print(graph[prev],dist[next],next)
            d1 = d + 1
            if dist[i] > d1:
                dist[i] = d1
                heappush(que, (d1, i))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)

Buggy submission (verdict: Runtime Error):
from collections import deque
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = deque()
d.appendleft([0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,ver = d.popleft()
        check[ver][num%3] = 1
        num = num+1
        #cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num%3 == 0:
                print(num//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.append([num,uv[ver][j]])
                
print(-1)

Buggy submission (verdict: Runtime Error):
from collections import deque
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = deque()
d.appendleft([0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,ver = d.popleft()
        check[ver][num] = 1
        num = num+1
        #cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num%3 == 0:
                print(num//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.append([num,uv[ver][j]])
                
print(-1)

Buggy submission (verdict: Runtime Error):
from collections import deque
import queue
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = queue.Queue()
d.put([0,0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,cnt,ver = d.get()
        check[ver][num] = 1
        num = (num+1)%3
        cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num == 0:
                print(cnt//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.put([num,cnt,uv[ver][j]])
                
print(-1)