Submission #4631175

---

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 (vf, cp) in visited:
            continue
        if cp == cf:
            dist[(vf, cf)] = min(dist.get((vf, cf), 10**9), dist.get((vn, cp), 10**9))
            Q.append((vf, cf))
        else:
            dist[(vf, cf)] = min(dist.get((vf, cf), 10**9), 1 + dist.get((vn, cp), 10**9))
            Q.appendleft((vf, cf))
L = [dist.get((N, c), 10**9) for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

Submission Info

Judge Result