Problem:
 Score : 600 points    Problem Statement Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N . Each line is operated by a company. Each company has an identification number.  The i -th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i .  You can change trains at a station where multiple lines are available.  The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.  Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.      Constraints  2 \leq N \leq 10^5  0 \leq M \leq 2×10^5  1 \leq p_i \leq N  (1 \leq i \leq M)  1 \leq q_i \leq N  (1 \leq i \leq M)  1 \leq c_i \leq 10^6  (1 \leq i \leq M)  p_i \neq q_i  (1 \leq i \leq M)         Input The input is given from Standard Input in the following format:  N  M  p_1  q_1  c_1 : p_M  q_M  c_M       Output Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.        Sample Input 1 3 3
1 2 1
2 3 1
3 1 2      Sample Output 1 1  Use company 1 's lines: 1 → 2 → 3 . The fare is 1 yen.       Sample Input 2 8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5      Sample Output 2 2  First, use company 1 's lines: 1 → 3 → 2 → 5 → 6 . Then, use company 5 's lines: 6 → 7 → 8 . The fare is 2 yen.       Sample Input 3 2 0      Sample Output 3 -1

Solution (Python):
def main():
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()

Solution (Python):
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from collections import deque

def solve():
    dist = [inf] * len(to)
    q = deque()
    q.append((0, 0))
    dist[0] = 0
    while q:
        d, i = q.popleft()
        if d > dist[i]: continue
        if i < n:
            for j in to[i]:
                if dist[j] <= d + 1: continue
                dist[j] = d + 1
                q.append((d + 1, j))
        else:
            for j in to[i]:
                if j == n - 1:
                    print(dist[i])
                    exit()
                if dist[j] <= d: continue
                dist[j] = d
                q.appendleft((d, j))
    print(-1)

inf=10**9
n,m=MI()
to=[]
uctoi={}

for u in range(n):
    to.append([])
    uctoi[u,0]=u

for _ in range(m):
    u,v,c=MI()
    u,v=u-1,v-1
    if (u,c) not in uctoi:
        i=uctoi[u,c]=len(to)
        to.append([])
        to[i].append(u)
        to[u].append(i)
    else:i=uctoi[u,c]
    if (v,c) not in uctoi:
        j=uctoi[v,c]=len(to)
        to.append([])
        to[j].append(v)
        to[v].append(j)
    else:j=uctoi[v,c]
    to[i].append(j)
    to[j].append(i)



solve()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.buffer.readline


def bfs():
    dp[sup_v][0] = 1
    q1 = deque([sup_v])
    q2 = deque([0])
    while q1:
        v1 = q1.popleft()
        v2 = q2.popleft()
        for tmp in graph[v1 * OFFSET + v2]:
            nxt_v1, nxt_v2 = divmod(tmp, OFFSET)
            if nxt_v1 == -1:
                cost = 1
            else:
                cost = 0
            if nxt_v1 not in dp:
                dp[nxt_v1] = {}
            if nxt_v2 not in dp[nxt_v1]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q1.appendleft(nxt_v1)
                    q2.appendleft(nxt_v2)
                else:
                    q1.append(nxt_v1)
                    q2.append(nxt_v2)
            elif dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q1.appendleft(nxt_v1)
                    q2.appendleft(nxt_v2)
                else:
                    q1.append(nxt_v1)
                    q2.append(nxt_v2)
    
n, m = map(int, input().split())
INF = 10 ** 18
OFFSET = 10 ** 6


sup_v = -1
graph = {sup_v * OFFSET: []}
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c * OFFSET + a not in graph:
        graph[c * OFFSET + a] = []
        graph[c * OFFSET + a].append(sup_v * OFFSET + a)
    if c * OFFSET + b not in graph:
        graph[c * OFFSET + b] = []
        graph[c * OFFSET + b].append(sup_v * OFFSET + b)
    if sup_v * OFFSET + a not in graph:
        graph[sup_v * OFFSET + a] = []
    if sup_v * OFFSET + b not in graph:
        graph[sup_v * OFFSET + b] = []

    graph[c * OFFSET + a].append(c * OFFSET + b)
    graph[c * OFFSET + b].append(c * OFFSET + a)
    graph[sup_v * OFFSET + a].append(c * OFFSET + b)
    graph[sup_v * OFFSET + b].append(c * OFFSET + a)


dp = {sup_v: {}}
bfs()
ans = INF
for i in dp:
    for j in dp[i]:
        if j == n - 1:
            ans = min(dp[i][j], ans)   
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m = map(int, readline().split())

g = {}

for _ in range(m):
    p,q,c = map(int, readline().split())
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque, defaultdict

    n, m = map(int, readline().split())
    graph = [defaultdict(set) for _ in range(n + 1)]
    for _ in range(m):
        p, q, c = map(int, readline().split())
        graph[p][c].add(q)
        graph[q][c].add(p)
    q = deque([(1, 0, -1)])
    vis = set()
    while q:
        now, v, c = q.popleft()
        if now == n:
            print(v)
            exit()
        if (now, c) in vis:
            continue
        vis.add((now, c))
        if c == 0:
            for cc in graph[now]:
                for next in graph[now][cc]:
                    if (next, cc) not in vis:
                        q.append((next, v + 1, cc))
        else:
            for next in graph[now][c]:
                if (next, c) not in vis:
                    q.appendleft((next, v, c))
            if (now, 0) not in vis:
                q.appendleft((now, v, 0))
    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

Solution (Python):
class UnionFindVerSize():
    def __init__(self,init):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, len(init))]
        
        self._size = [1] * len(init)
        self._dict ={key:0 for key in init}
        for i in range(len(init)):
            v=init[i]
            self._dict[v]=i

    def find_root(self, x,key):
        """ xの木の根(xがどのグループか)を求める """
        if key==1:
            x=self._dict[x]
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x],0) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        x=self._dict[x]
        y=self._dict[y]
        gx = self.find_root(x,0)
        gy = self.find_root(y,0)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        x=self._dict[x]
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x,0)]

    def is_same_group(self, x, y):
        x=self._dict[x]
        y=self._dict[y]
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x,0) == self.find_root(y,0)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i,0) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
company={}
cedge={}
node=N
edge={i:[] for i in range(N)}
for i in range(M):
    u,v,c=map(int,input().split())
    edge[u-1].append((v-1,1))
    edge[v-1].append((u-1,1))
    if c-1 not in company:
        company[c-1]=[]
        cedge[c-1]=[]
    company[c-1].append(u-1)
    company[c-1].append(v-1)
    cedge[c-1].append((u-1,v-1))

for i in company:
    uf=UnionFindVerSize(company[i])
    for u,v in cedge[i]:
        uf.unite(u,v)
    data={}
    for v in company[i]:
        p=uf.find_root(v,1)
        if p not in data:
            data[p]=[]
        data[p].append(v)
    for p in data:
        edge[node]=[]
        for v in data[p]:
            edge[v].append((node,0))
            edge[node].append((v,1))
        node+=1

from collections import deque
dist=[10**20]*node
dist[0]=0
que=deque([(0,0)])
while que:
    v,d=que.popleft()
    for nv,c in edge[v]:
        if dist[nv]>d+c:
            if c==1:
                dist[nv]=d+c
                que.append((nv,d+c))
            else:
                dist[nv]=d+c
                que.appendleft((nv,d+c))


ans=dist[N-1]
print(ans if ans!=10**20 else -1)

Solution (Python):
def resolve():
    def Dijkstra(s, g):
        from collections import deque
        d = {s}
        queue = deque()
        for q in edge[s]:
            queue.append((1, q))
        while queue:
            dist, point = queue.popleft()
            if point in d:
                continue
            d.add(point)
            if point == g:
                return dist
            for nextp in edge[point]:
                if not nextp in d:
                    if not -1 in point or -1 in nextp:
                        queue.appendleft((dist, nextp))
                    else:
                        queue.append((dist + 1, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, c)].add((q, c))
        edge[(q, c)].add((p, c))
        edge[(p, c)].add((p, -1))
        edge[(q, c)].add((q, -1))
        edge[(p, -1)].add((p, c))
        edge[(q, -1)].add((q, c))
    print(Dijkstra((0, -1), (n - 1, -1)))


if __name__ == '__main__':
    resolve()

Solution (Python):
import heapq

INF = 1000000000


def dijkstra(G, d, s):
    h = []
    d[s] = 0
    heapq.heappush(h, (0, s))

    while len(h) != 0:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in G[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(h, (d[e[0]], e[0]))


def main():
    N, M = map(int, input().split())
    p = [0] * M
    q = [0] * M
    c = [0] * M
    for i in range(M):
        p[i], q[i], c[i] = map(int, input().split())
        p[i] -= 1
        q[i] -= 1
    plat = []
    for i in range(N):
        plat.append(dict())
    v_count = 0
    for i in range(M):
        p1 = plat[p[i]]
        if not c[i] in p1:
            p1[c[i]] = v_count
            v_count += 1
        p2 = plat[q[i]]
        if not c[i] in p2:
            p2[c[i]] = v_count
            v_count += 1
    for i in range(N):
        plat[i][-1] = v_count
        v_count += 1

    G = [[] for _ in range(v_count)]
    for i in range(M):
        p1 = plat[p[i]][c[i]]
        q1 = plat[q[i]][c[i]]
        G[p1].append((q1, 0))
        G[q1].append((p1, 0))
    for i in range(N):
        out = plat[i][-1]
        for v in plat[i].values():
            if v == -1:
                continue
            G[v].append((out, 0))
            G[out].append((v, 1))

    start = plat[0][-1]
    goal = plat[N - 1][-1]

    d = [INF for _ in range(v_count)]

    dijkstra(G, d, start)

    if d[goal] == INF:
        print(-1)
    else:
        print(d[goal])


if __name__ == '__main__':
    main()

Solution (Python):
import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.buffer.readline()[:-1]

class DijkstraList():
	
	
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append((q-1 + t * n, 0))
	edges[q-1 + t * n].append((p-1 + t * n, 0))
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append((p-1 + 0 * n, 0))
		edges[p-1 + 0 * n].append((p-1 + t * n, 1))
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append((q-1 + 0 * n, 0))
		edges[q-1 + 0 * n].append((q-1 + t * n, 1))

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)

Solution (Python):
import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	
	
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append((q-1 + t * n, 0))
	edges[q-1 + t * n].append((p-1 + t * n, 0))
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append((p-1 + 0 * n, 0))
		edges[p-1 + 0 * n].append((p-1 + t * n, 1))
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append((q-1 + 0 * n, 0))
		edges[q-1 + 0 * n].append((q-1 + t * n, 1))

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)

Solution (Python):
from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
C = set()

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, 0, 0)]
while que:
    dist, f, now = heappop(que)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, f + 1, to))
        if minDist[to] == d:
            minDistList[to].add(c)

for _ in range(2):
    que = [(minDist[i], 0, i) for i in range(N)]
    heapify(que)
    while que:
        dist, f, now = heappop(que)

        for to, c in edges[now]:
            d = dist
            if not c in minDistList[now]:
                d += 1
            if minDist[to] > d:
                minDist[to] = d
                minDistList[to] = set()
                heappush(que, (d, f + 1, to))
            if minDist[to] == d:
                minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
n,m = map(int, input().split())
link = defaultdict(list)
chg=10**8
for _ in range(m):
    p,q,c=map(int, input().split())
    link[p].append([p+chg*c,1])
    link[p+chg*c].append([p,1])

    link[q+chg*c].append([p+chg*c,0])
    link[p+chg*c].append([q+chg*c,0])

    link[q+chg*c].append([q,1])
    link[q].append([q+chg*c,1])

def dks(g,start):
    INF=float('inf')
    visited = set()
    hq = []
    heappush(hq, (0,start))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        for j, t in g[i]:
            if j in visited:
                continue
            if j==n:
                return (shortest+t)//2
            heappush(hq, (shortest + t, j))
    return -1
ans=dks(link,1)
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque
INF = 10**9

n, m = map(int, input().split())
pqc = []

seen = set()
for i in range(n):
    seen.add((i, 0))
for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1
    pqc.append((p, q, c))
    seen.add((p, c))
    seen.add((q, c))
comp = dict()
for i, node in enumerate(seen):
    comp[node] = i

edge = [[] for _ in range(len(comp))]
for key in comp.keys():
    v, c = key
    if c != 0:
        frm = comp[(v, c)]
        too = comp[(v, 0)]
        edge[frm].append((too, 0))
        edge[too].append((frm, 1))

for p, q, c in pqc:
    frm = comp[(p, c)]
    too = comp[(q, c)]
    edge[frm].append((too, 0))
    edge[too].append((frm, 0))

class BFS:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = deque()

    def calc(self, start):
        self.dist[start] = 0
        self.q.append((0, start))
        while len(self.q) != 0:
            prov_cost, src = self.q.popleft()
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    if cost == 1:
                        self.q.append((self.dist[dest], dest))
                    else:
                        self.q.appendleft((self.dist[dest], dest))
        return self.dist

bfs = BFS(edge)
bfs.calc(comp[(0, 0)])
ans = bfs.dist[comp[(n-1, 0)]]
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            for c in links[v]:
                for u in links[v][c]:
                    if (u, c) not in visited:
                        q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) not in visited:
                    q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print(bfs01(0, n - 1, links))

Solution (Python):
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            lv = links[v]
            for c in lv:
                for u in lv[c]:
                    if (u, c) in visited:
                        continue
                    q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) in visited:
                    continue
                q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print(bfs01(0, n - 1, links))

Solution (Python):
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            q.extend((d + 1, u, c) for c in links[v] for u in links[v][c] if (u, c) not in visited)
        else:
            q.extendleft((d, u, e) for u in links[v][e] if (u, e) not in visited)
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print(bfs01(0, n - 1, links))

Solution (Python):
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            q.extend((d + 1, u, c) for c, us in links[v].items() for u in us if (u, c) not in visited)
        else:
            q.extendleft((d, u, e) for u in links[v][e] if (u, e) not in visited)
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print(bfs01(0, n - 1, links))

Solution (Python):
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            for c, us in links[v].items():
                for u in us:
                    if (u, c) in visited:
                        continue
                    q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) in visited:
                    continue
                q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print(bfs01(0, n - 1, links))

Solution (Python):
import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            for c in links[v]:
                for u in links[v][c]:
                    if (u, c) in visited:
                        continue
                    q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) in visited:
                    continue
                q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print(bfs01(0, n - 1, links))

Solution (Python):
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
inf = 10**9+7
def dijkstra(N, s, Edge):    
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dn + df < dist[vf]:
                dist[vf] = dn + df
                hp(Q, (dn + df,vf))
    return dist

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


N, M = map(int, readline().split())

Edge = []
VS = set(range(N))
geta = 20
Edge = [tuple(map(int, readline().split())) for _ in range(M)]
for a, b, c in Edge:
    a -= 1
    b -= 1
    VS |= {(c<<geta) | a, (c<<geta) | b}
   
_, Cv = compress(list(VS))

Vnum = len(Cv)

nEdge = [[] for _ in range(Vnum)]

for a, b, c in Edge:
    a -= 1
    b -= 1
    ca = Cv[(c<<geta) | a]
    cb = Cv[(c<<geta) | b]
    nEdge[ca].append((0, cb))
    nEdge[cb].append((0, ca))
    nEdge[a].append((1, ca))
    nEdge[ca].append((0, a))
    nEdge[b].append((1, cb))
    nEdge[cb].append((0, b))

dist = dijkstra(Vnum, 0, nEdge)
if dist[N-1] >= inf:
    dist[N-1] = -1
print(dist[N-1])