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



Sample input:
3 3
1 2 1
2 3 1
3 1 2


Sample output:
1

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,M = map(int,readline().split())
if M == 0:
    print(-1)
    exit()
m = map(int,read().split())
P,Q,C = zip(*zip(m,m,m))

V = []
V += [p<<32 for p in range(1,N+1)]
V += [(p<<32)+c for p,c in zip(P,C)]
V += [(q<<32)+c for q,c in zip(Q,C)]
V = set(V)
label = {x:i for i,x in enumerate(V)}
start = label[1<<32]
goal = label[N<<32]

N = len(V)
graph = [[] for _ in range(N)]
for p,q,c in zip(P,Q,C):
    v0 = label[p<<32]; v1 = label[(p<<32)+c]
    w0 = label[q<<32]; w1 = label[(q<<32)+c]
    graph[v0].append((v1,1))
    graph[w0].append((w1,1))
    graph[v1].append((v0,0))
    graph[w1].append((w0,0))
    graph[v1].append((w1,0))
    graph[w1].append((v1,0))

INF = 10 ** 10
dist = [INF] * N
dist[start] = 0
q = deque([start])
ar = q.append; al = q.appendleft
pl = q.popleft
while q:
    v = pl()
    for w,cost in graph[v]:
        dw = dist[v] + cost
        if dw >= dist[w]:
            continue
        dist[w] = dw
        if not cost:
            al(w)
        else:
            ar(w)

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)

Submission status: Accepted

Solution code:
def dijkstra_heap(s,edge,mask):
    dist = defaultdict(lambda: float("inf"))
    q = [s]  # 0 が会社に属していない状態
    dist[s] = 0
    d = 0; q0 = []; q1 = []
    while q:
        for x in q:
            if x & mask == 0:
                for y in edge[x]:
                    if dist[y[1]] <= d + y[0]:
                        continue
                    dist[y[1]] = d + y[0]
                    q1.append(y[1])
            else:
                for y in edge[x]:
                    if dist[y[1]] <= d+ y[0]:
                        continue
                    dist[y[1]] = d+ y[0]
                    q0.append(y[1])
        if q0:
            q = q0
            q0 = []
            continue
        q = q1
        q1 = []
        d += 1
    return dist

def examE(inf):
    N, M = LI()
    edge = defaultdict(list)
    # edge[i] : iから出る道の[重み,行先]の配列
    L = 32
    Mask = (1 << L) - 1
    for i in range(M):
        p, q, c = map(int, input().split())
        p -=1; q -=1
        p <<= L
        q <<= L
        #同じ路線だとコスト０ 乗るときだけコスト１
        edge[p].append((1,p + c))
        edge[p + c].append((0,p))
        edge[q].append((1,q + c))
        edge[q + c].append((0,q))
        edge[p + c].append((0,q + c))
        edge[q + c].append((0,p + c))
    start = 0
    goal = (N-1) << L
    res = dijkstra_heap(start, edge, Mask)
#    print(res)
    ans = res[goal]
    if ans == inf:
        ans = -1
    print(ans)


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(inf)

Submission status: Accepted

Solution code:
def dijkstra_heap(s,edge,mask):
    dist = defaultdict(lambda: float("inf"))
    q = [s]  # 0 が会社に属していない状態
    dist[s] = 0
    d = 0; q0 = []; q1 = []
    while q:
        for x in q:
            if x & mask == 0:
                for y in edge[x]:
                    if dist[y[1]] <= d + y[0]:
                        continue
                    dist[y[1]] = d + y[0]
                    q1.append(y[1])
            else:
                for y in edge[x]:
                    if dist[y[1]] <= d:
                        continue
                    dist[y[1]] = d
                    q0.append(y[1])
        if q0:
            q = q0
            q0 = []
            continue
        q = q1
        q1 = []
        d += 1
    return dist

def examE(inf):
    N, M = LI()
    edge = defaultdict(list)
    # edge[i] : iから出る道の[重み,行先]の配列
    L = 32
    Mask = (1 << L) - 1
    for i in range(M):
        p, q, c = map(int, input().split())
        p -=1; q -=1
        p <<= L
        q <<= L
        edge[p].append((1,p + c))
        edge[p + c].append((0,p))
        edge[q].append((1,q + c))
        edge[q + c].append((0,q))
        #同じ路線だとコスト０
        edge[p + c].append((0,q + c))
        edge[q + c].append((0,p + c))
    start = 0
    goal = (N-1) << L
    res = dijkstra_heap(start, edge, Mask)
#    print(res)
    ans = res[goal]
    if ans == inf:
        ans = -1
    print(ans)


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(inf)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    p, q, c = map(int, input().split())
    G[(p-1, c-1)].append((p-1, -1))
    G[(q-1, c-1)].append((q-1, -1))
    G[(p-1, -1)].append((p-1, c-1))
    G[(q-1, -1)].append((q-1, c-1))
    G[(p-1, c-1)].append((q-1, c-1))
    G[(q-1, c-1)].append((p-1, c-1))


dist = defaultdict(lambda :-1)
que = deque([(0, -1)])
dist[(0, -1)] = 0
while que:
    v = que.pop()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]<0:
            if nv[1] == -1:
                dist[nv] = d+1
                que.appendleft(nv)
            else:
                dist[nv] = d
                que.append(nv)
print(dist[(N-1, -1)])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from heapq import heappush, heappop
from collections import defaultdict, deque

def main():
  n, m = map(int, input().split())
  edges = [[] for _ in range(n)]
  cedges = defaultdict(lambda: [])
  for _ in range(m):
    p, q, c = map(int, input().split())
    edges[p-1].append((q-1, c))
    edges[q-1].append((p-1, c))
    cedges[p-1, c].append(q-1)
    cedges[q-1, c].append(p-1)

  ans = defaultdict(lambda: float('inf'))
  ans[0, -1] = 0  # ノード、路線
  que = deque([(0, 0, -1)])  # 距離、ノード、路線
  while len(que) > 0:
    d, u, c = que.popleft()
    if ans[u, c] < d:  # 更新しない
      continue
    if c < 0:
      for t, c2 in edges[u]:
        if d + 1 < ans[t, c2]:
          ans[t, c2] = d + 1
          que.append((d+1, t, c2))
    else:
      for t in cedges[u, c]:
        if d < ans[t, c]:
          ans[t, c] = d
          que.appendleft((d, t, c))
      if d < ans[u, -1]:
        ans[u, -1] = d
        que.appendleft((d, u, -1))
  try:
    print(min(d for (u, _), d in ans.items() if u == n-1))
  except ValueError:
    print(-1)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# https://juppy.hatenablog.com/entry/2019/04/10/ARC061_-_E_%E3%81%99%E3%81%AC%E3%81%91%E5%90%9B%E3%81%AE%E5%9C%B0%E4%B8%8B%E9%89%84%E6%97%85%E8%A1%8C_-_Python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
# 参考にさせていただきました。

from collections import deque, defaultdict

chg = 10**6
n, m = map(int, input().split())
edges = defaultdict(set)
# m=0のためにdefaultdictにしておくべき
visited = defaultdict(set)
for i in range(m):
    p, q, c = map(int, input().split())
    edges[p+c*chg].add(q+c*chg)
    edges[q+c*chg].add(p+c*chg)
    edges[p].add(p+c*chg)
    edges[q].add(q+c*chg)
    edges[p+c*chg].add(p)
    edges[q+c*chg].add(q)
    visited[p] = False
    visited[q] = False
    visited[p+c*chg] = False
    visited[q+c*chg] = False

ans = float("inf")
que = deque()
# now, dist
que.append((1, 0))
# 今求めるのはendの距離だけなので、dist配列はいらない
# さらに、距離は0/1なのでheapで辺を管理する必要もなく、0なら最短確定なので先に、1ならその時点での最長なので後ろにすれば良い
while que:
    now, dist = que.popleft()
    if visited[now]:
        continue
    visited[now] = True
    if now == n:
        ans = dist
        break
    for to in edges[now]:
        # 駅→ホーム
        if now < chg and to > chg:
            que.append((to, dist+1))
        else:
            que.appendleft((to, dist))
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
q0 = []
q1 = []
while q:
    for x in q:
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                q1.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q0.append(y)
    if q0:
        q = q0
        q0 = []
        continue
    q = q1
    q1 = []
    d += 1

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()
"""))

Submission status: Accepted

Solution code:
def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict,deque
n,m=map(int,input().split())
route=10**6
Edges=defaultdict(set)
Visited=defaultdict(bool)
for _ in range(m):
    p,q,c=map(int,input().split())
    Edges[p].add(p+c*route)
    Edges[p+c*route].add(p)
    Edges[p+c*route].add(q+c*route)
    Edges[q+c*route].add(p+c*route)
    Edges[q].add(q+c*route)
    Edges[q+c*route].add(q)
q=deque()
q.append((1,0))
cost=-1
while q:
    fr,c=q.popleft()
    Visited[fr]=True
    if fr==n:
        cost=c
        break
    for to in Edges[fr]:
        if Visited[to]:
            continue
        if fr<=10**5 and to>route:
            q.append((to,c+1))
        else:
            q.appendleft((to,c))
print(cost)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict,deque

def main():
    input = sys.stdin.readline
    n,m = map(int,input().split())
    #+路線*chg : その路線ホーム
    chg = 10**6

    edge=defaultdict(set)
    used =defaultdict(bool)
    for i in range(m):
        p,q,c = map(int,input().split())
        edge[p].add(p+c*chg)
        edge[p+c*chg].add(p)
        edge[p+c*chg].add(q+c*chg)
        edge[q+c*chg].add(p+c*chg)
        edge[q].add(q+c*chg)
        edge[q+c*chg].add(q)
        used[p] = False
        used[q] = False
        used[p+c*chg] = False
        used[q+c*chg] = False

    edgelist = deque()
    edgelist.append((1,0))
    res = float("inf")
    while len(edgelist):
        x,cost = edgelist.pop()
        used[x] = True

        if x == n:
            res = cost
            break
        for e in edge[x]:
            if used[e]:
                continue
            #行先が改札
            if x <= 10**5 and chg <= e:
                edgelist.appendleft((e,cost+1))
            else:
                edgelist.append((e,cost))
            
    if res == float("inf"):
        print(-1)
    else:
        print(res)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict,deque
input = sys.stdin.readline
n,m = map(int,input().split())
#+路線*chg : その路線ホーム
chg = 10**6

edge=defaultdict(set)
used =defaultdict(bool)
for i in range(m):
    p,q,c = map(int,input().split())
    edge[p].add(p+c*chg)
    edge[p+c*chg].add(p)
    edge[p+c*chg].add(q+c*chg)
    edge[q+c*chg].add(p+c*chg)
    edge[q].add(q+c*chg)
    edge[q+c*chg].add(q)
    used[p] = False
    used[q] = False
    used[p+c*chg] = False
    used[q+c*chg] = False

edgelist = deque()
edgelist.append((1,0))
res = float("inf")
while len(edgelist):
    x,cost = edgelist.pop()
    used[x] = True

    if x == n:
        res = cost
        break
    for e in edge[x]:
        if used[e]:
            continue
        #行先が改札
        if x <= 10**5 and chg <= e:
            edgelist.appendleft((e,cost+1))
        else:
            edgelist.append((e,cost))
        
if res == float("inf"):
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def bfs01(g, s):
    d = {}
    for v in g.keys():
        d[v] = sys.maxsize
    d[s] = 0

    if s not in d:
        return d
    q = deque()
    q.append((d[s], s))

    NM = 1 << 30
    while q:
        _, u = q.popleft()
        for v in g[u]:
            if v > NM:
                c = 0
            else:
                c = 1
            alt = c + d[u]
            if d[v] > alt:
                d[v] = alt
                if c == 0:
                    q.appendleft((d[v], v))
                else:
                    q.append((d[v], v))
    return d


@mt
def slv(N, M):

    g = defaultdict(list)
    NM = 30
    for _ in range(M):
        p, q, c = input().split()
        p = int(p)
        q = int(q)
        c = int(c)

        cp = (c << NM) + p
        cq = (c << NM) + q
        g[cp].append(cq)
        g[cq].append(cp)
        g[cp].append(p)
        g[cq].append(q)
        g[p].append((cp))
        g[q].append((cq))

    d = bfs01(g, 1)
    return -1 if N not in d or d[N] == sys.maxsize else d[N]


def main():
    N, M = read_int_n()

    print(slv(N, M))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def tall(self):
        d = collections.defaultdict(list)
        for i in range(len(self.table)):
            d[self.find(i)].append(i)
        return d

def main():
    M = 2**17
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for p,q,c in a:
        pc = p+c*M
        qc = q+c*M
        pm = p-M
        qm = q-M
        e[pc].append(qc)
        e[qc].append(pc)
        e[pm].append(pc)
        e[qm].append(qc)
        e[pc].append(pm)
        e[qc].append(qm)

    def search():
        d = collections.defaultdict(lambda: inf)
        s = 1-M
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = set()
        while len(q):
            k, u = heapq.heappop(q)
            if u in v:
                continue
            v.add(u)
            if u < 0:
                for uv in e[u]:
                    if uv in v:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            else:
                if u % M == n:
                    return k

                for uv in e[u]:
                    if uv in v:
                        continue
                    if d[uv] > k:
                        d[uv] = k
                        heapq.heappush(q, (k, uv))

        return -1

    return search()



print(main())

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
edgesc = defaultdict(lambda: [])
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))
  edgesc[p, c].append(q)
  edgesc[q, c].append(p)

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d:
      continue
    if c < 0:
      for (t, c2) in edges[u]:
        if d + 1 < result[t, c2]:
          result[t, c2] = d + 1
          que.append((d + 1, t, c2))
    else:
      for t in edgesc[u, c]:
        if d < result[t, c]:
          result[t, c] = d
          que.appendleft((d, t, c))
      if d < result[u, -1]:
        result[u, -1] = d
        que.appendleft((d, u, -1))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
# Companies of Station
C_of_S = {}

# def Union-find
parent = [-1]*M
def root(x):
    if (parent[x] < 0): return x
    else:
        parent[x] = y = root(parent[x])
        return y

def unite(x, y):
    px = root(x); py = root(y);
    if (px == py): return False
    if (parent[px] > parent[py]):
        px = root(y); py = root(x);
    parent[px] += parent[py]
    parent[py] = px
    return True

# Union-find
pqcs = []
for i in range(M):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1;
    pqcs += [(p, q, c)]
    # The first
    if not c in F_C_of_S[p]:
        F_C_of_S[p][c] = i
    # else
    else:
        unite(F_C_of_S[p][c], i)
    C_of_S.setdefault(p, set()).add(c)
    # The first
    if not (c in F_C_of_S[q]):
        F_C_of_S[q][c] = i
    # else
    else:
        unite(F_C_of_S[q][c], i)
    C_of_S.setdefault(q, set()).add(c)

# stations of company
S_of_C = {}
for i in range(M):
    p, q, c = pqcs[i]
    c_set = S_of_C.setdefault(root(i), set())
    c_set.add(p); c_set.add(q);

Q = deque([(0, 0, 0)])
# cost to go to the stations from station_0
dist = [float('inf')] * N
dist[0] = 0

gdist = [float('inf')] * M

while Q:
    cost, v, flag = Q.popleft()
    if not (flag):  # (flag == 0) then gdist_update
        for l in F_C_of_S[v].values():
            l = root(l)
            if (cost < gdist[l]):
                gdist[l] = cost
                Q.appendleft((cost, l, 1))
    else:  # (flag == 1) then dist_update
        for s in S_of_C[v]:
            if (cost + 1 < dist[s]):
                dist[s] = cost + 1
                Q.append((cost + 1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

#def Union-find
parent = [-1]*M
def root(x):
	if (parent[x] < 0): return x
	else:
		parent[x] = y = root(parent[x])
		return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	return True


#Union-find
pqcs = []
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]: F_C_of_S[p][c] = i
	#else
	else: unite(F_C_of_S[p][c], i)
	C_of_S.setdefault(p, set()).add(c)
	
	#The first
	if not (c in F_C_of_S[q]):F_C_of_S[q][c] = i
	#else
	else: unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)

#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = pqcs[i]
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)


Q = deque([(0, 0, 0)])
#cost to go to the stations from station_0
dist = [float('inf')]*N
dist[0] = 0

gdist = [float('inf')]*M

while Q:
	cost, v, flag = Q.popleft()
	
	if not (flag):#(flag == 0) then gdist_update
		if (dist[v] < cost) or (v not in C_of_S):
			continue
		for l in F_C_of_S[v].values():
			l = root(l)
			if (cost < gdist[l]):
				gdist[l] = cost
				Q.appendleft((cost, l, 1))
	
	else:#(flag == 1) then dist_update
		if (gdist[v] < cost) or (v not in S_of_C):
			continue
		for s in S_of_C[v]:
			if (cost+1 < dist[s]):
				dist[s] = cost+1
				Q.append((cost+1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)