Submission #4631568

---

Source Code Expand

import sys
from collections import deque
N, M = map(int, input().split())
Edge = [[] for _ in range(N+1)]
comp = set()
def f(a,b):
    return a+10**5*b
for _ in range(M):
    p, q, c = map(int, sys.stdin.readline().split())
    Edge[p].append(f(q, c))
    Edge[q].append(f(p, c))
    comp.add(c)
dist = {f(1, 0): 0}
Q = deque()
Q.append(1)
visited = set()
while Q:
    cp, vn = divmod(Q.pop(), 10**5)
    if f(vn, cp) in visited:
        continue
    visited.add(f(vn, cp))
    for cvi in Edge[vn]:
        cf, vf = divmod(cvi, 10**5)
        if f(vf, cp) in visited:
            continue
        if cp == cf:
            dist[f(vf, cf)] = min(dist.get(f(vf, cf), 10**9), dist.get(f(vn, cp), 10**9))
            Q.append(f(vf, cf))
        else:
            dist[f(vf, cf)] = min(dist.get(f(vf, cf), 10**9), 1 + dist.get(f(vn, cp), 10**9))
            Q.appendleft(f(vf, cf))
L = [dist.get(f(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