Submission #4631011

---

Source Code Expand

import sys
from collections import deque
N, M = map(int, input().split())
Edge = [[] for _ in range(N+1)]
comp = set()
for _ in range(M):
    p, q, c = map(int, sys.stdin.readline().split())
    Edge[p].append((q, c))
    Edge[q].append((p, c))
    comp.add(c)
dist = {(1, 0): 0}
Q = deque()
Q.append((1, 0))
visited = set()
while Q:
    vn, cp = Q.pop()
    if (vn, cp) in visited:
        continue
    visited.add((vn, cp))
    for vf, cf in Edge[vn]:
        if cp == cf:
            dist[(vf, cf)] = min(dist.get((vf, cf), float('inf')), dist.get((vn, cp), float('inf')))
            Q.append((vf, cf))
        else:
            dist[(vf, cf)] = min(dist.get((vf, cf), float('inf')), 1 + dist.get((vn, cp), float('inf')))
            Q.appendleft((vf, cf))

print(min([dist.get((N, c), float('inf')) for c in comp]))

Submission Info

Judge Result