Problem p04003 (python)

Fixed submission:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque, defaultdict

n,m = li()
mod = 10**7

table = defaultdict(set)
visit = defaultdict(int)

for i in range(m):
    a,b,c = li()
    
    table[a].add(a + c*mod)
    table[b].add(b + c*mod)
    table[a + c*mod].add(a)
    table[b + c*mod].add(b)
    table[a + c*mod].add(b + c*mod)
    table[b + c*mod].add(a + c*mod)
    
    visit[a] = 0
    visit[b] = 0
    visit[b + c*mod] = 0
    visit[a + c*mod] = 0
    
que = deque()
que.append((1,0))

visit[1] = 1
ans = mod

while que:
    x, cost = que.popleft()
    visit[x] = 1
    
    if x == n:
        ans = min(ans, cost)
        break
    
    for y in table[x]:
        if visit[y] == 1:
            continue
        
        if x <= 10**5 and mod <= y:
            que.append((y, cost+1))
            
        else:
            que.appendleft((y, cost))
        
print(-1 if ans == mod else ans)

Buggy submission (verdict: Runtime Error):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph: list, start, INF, num2node, destination) -> int:
    n = len(graph)
    dist = [INF]*n
    visited = [False]*n
    
    dist[start] = 0
    que = [(dist[start], start)]
    
    while que:
        cost, cur = heappop(que)
        
        if visited[cur]:
            continue
        
        if num2node[cur][0] == destination:
            return cost
        
        visited[cur] = True
        
        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))
      
    return INF

def get_nodenum(station, company, keyset, node2num):
    if (station, company) not in keyset:
        keyset.add((station, company))
        keyslen = len(keyset)-1
        node2num.update({(station, company): keyslen})
        
        return keyslen
    
    else:
        return node2num[(station, company)]
    

n,m = li()

graph = [[] for _ in [0]*(5*(10**5))]
node2num = {}
num2node = {}
keyset = set()

for _ in range(m):
    p,q,c = li()

    # ノードの登録
    pc_nodenum = get_nodenum(p,c,keyset,node2num)
    qc_nodenum = get_nodenum(q,c,keyset,node2num)
    
    pz_nodenum = get_nodenum(p,0,keyset,node2num)
    qz_nodenum = get_nodenum(q,0,keyset,node2num)
    

    # 隣接リストの更新
    graph[pc_nodenum].append((qc_nodenum, 0))
    graph[qc_nodenum].append((pc_nodenum, 0))
    
    graph[pc_nodenum].append((pz_nodenum, 0))
    graph[qc_nodenum].append((qz_nodenum, 0))
    
    graph[pz_nodenum].append((pc_nodenum, 1))
    graph[qz_nodenum].append((qc_nodenum, 1))
    
num2node = {ni: (stati, compi) for (stati, compi), ni in node2num.items()}

INF = 1<<62
start = get_nodenum(1, 0, keyset, node2num)
ans = dijkstra(graph, start, INF, num2node, n)

print(-1 if ans == INF else ans)

Buggy submission (verdict: Runtime Error):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF]*n
    visited = [False]*n
    
    dist[start] = 0
    que = [(dist[start], start)]
    
    while que:
        cost, cur = heappop(que)
        
        if visited[cur]:
            continue
        
        visited[cur] = True
        
        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))
      
    return dist

def get_nodenum(station, company, keyset, node2num):
    if (station, company) not in keyset:
        keyset.add((station, company))
        keyslen = len(keyset)-1
        node2num.update({(station, company): keyslen})
        
        return keyslen
    
    else:
        return node2num[(station, company)]
    

n,m = li()

graph = [[] for _ in range(3*(10**5))]
node2num = {}
num2node = {}
keyset = set()

start = -1

for _ in range(m):
    p,q,c = li()

    # ノードの登録
    pc_nodenum = get_nodenum(p,c,keyset,node2num)
    qc_nodenum = get_nodenum(q,c,keyset,node2num)
    
    pz_nodenum = get_nodenum(p,0,keyset,node2num)
    qz_nodenum = get_nodenum(q,0,keyset,node2num)
    

    # 隣接リストの更新
    graph[pc_nodenum].append((qc_nodenum, 0))
    graph[qc_nodenum].append((pc_nodenum, 0))
    
    graph[pc_nodenum].append((pz_nodenum, 0))
    graph[qc_nodenum].append((qz_nodenum, 0))
    
    graph[pz_nodenum].append((pc_nodenum, 1))
    graph[qz_nodenum].append((qc_nodenum, 1))
    
num2node = {ni: (stati, compi) for (stati, compi), ni in node2num.items()}

INF = 1<<62
ans = INF

start = get_nodenum(1, 0, keyset, node2num)

dist = dijkstra(graph, start, INF)
for nodei in range(len(keyset)):
    if num2node[nodei][0] == n:
        ans = min(ans, dist[nodei])
        
print(-1 if ans == INF else ans)

Buggy submission (verdict: Runtime Error):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF]*n
    visited = [False]*n
    
    dist[start] = 1
    que = [(dist[start], start)]
    
    while que:
        cost, cur = heappop(que)
        
        if visited[cur]:
            continue
        
        visited[cur] = True
        
        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))
      
    return dist

def get_nodenum(station, company, keyset, node2num):
    if (station, company) not in keyset:
        keyset.add((station, company))
        keyslen = len(keyset)-1
        node2num.update({(station, company): keyslen})
        
        return keyslen
    
    else:
        return node2num[(station, company)]
    

n,m = li()

graph = [[] for _ in range(2*(10**5))]
node2num = {}
num2node = {}
keyset = set()

start = -1

for _ in range(m):
    p,q,c = li()
    
    # pかqが1ならスタートに設定
    
    # ノードの登録
    pc_nodenum = get_nodenum(p,c,keyset,node2num)
    qc_nodenum = get_nodenum(q,c,keyset,node2num)
    
    pz_nodenum = get_nodenum(p,0,keyset,node2num)
    qz_nodenum = get_nodenum(q,0,keyset,node2num)
    
    # pかqが1ならスタートに設定
    if p == 1:
        start = pc_nodenum
    elif q == 1:
        start = qc_nodenum

    # 隣接リストの更新
    graph[pc_nodenum].append((qc_nodenum, 0))
    graph[qc_nodenum].append((pc_nodenum, 0))
    
    graph[pc_nodenum].append((pz_nodenum, 0))
    graph[qc_nodenum].append((qz_nodenum, 0))
    
    graph[pz_nodenum].append((pc_nodenum, 1))
    graph[qz_nodenum].append((qc_nodenum, 1))
    
num2node = {ni: (stati, compi) for (stati, compi), ni in node2num.items()}

INF = 1<<62
ans = INF

if start == -1:
    print(-1)

else:
    dist = dijkstra(graph, start, INF)
    for nodei in range(len(keyset)):
        if num2node[nodei][0] == n:
            ans = min(ans, dist[nodei])
            
    print(-1 if ans == INF else ans)