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: Wrong Answer

Solution code:
from collections import deque
import sys
stdin=sys.stdin

ip=lambda: int(sp())
fp=lambda: float(sp())
lp=lambda:list(map(int,stdin.readline().split()))
sp=lambda:stdin.readline().rstrip()
yp=lambda:print('Yes')
np=lambda:print('No')

n,m=lp()
ans=[100000000 for _ in range(n)]
train=[[] for _ in range(n)]
for _ in range(m):
  p,q,l=lp()
  train[p-1].append([q-1,l])
  train[q-1].append([p-1,l])
  
ans[0]=1
d=train[0]
d=deque(d)
for i in train[0]:
  x,y=i
  ans[x]=1

tra_now=[-1 for _ in range(n)]

while d:
  v,now=d.popleft()
  tra_now[v]=now
  for i in train[v]:
    
    if i[1]==now:
      if ans[i[0]]>ans[v]:
        ans[i[0]]=ans[v]
        d.appendleft([i[0],now])
        
    else:
      if ans[i[0]]>ans[v]+1:
        ans[i[0]]=ans[v]+1
        d.append([i[0],i[1]])
        
if ans[n-1]==100000000:
  print(-1)
else:
  print(ans[n-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
stdin=sys.stdin

ip=lambda: int(sp())
fp=lambda: float(sp())
lp=lambda:list(map(int,stdin.readline().split()))
sp=lambda:stdin.readline().rstrip()
yp=lambda:print('Yes')
np=lambda:print('No')

n,m=lp()
ans=[100000000 for _ in range(n)]
train=[[] for _ in range(n)]
for _ in range(m):
  p,q,l=lp()
  train[p-1].append([q-1,l])
  train[q-1].append([p-1,l])
  
ans[0]=1
d=train[0]
d=deque(d)
for i in train[0]:
  x,y=i
  ans[x]=1

tra_now=[-1 for _ in range(n)]

while d:
  v,now=d.popleft()
  tra_now[v]=now
  for i in train[v]:
    if ans[i[0]]>ans[v]:
      if i[1]==now:
        ans[i[0]]=ans[v]
        d.appendleft([i[0],now])
        
      else:
        ans[i[0]]=ans[v]+1
        d.append([i[0],i[1]])
        
if ans[n-1]==100000000:
  print(-1)
else:
  print(ans[n-1])
  
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
stdin=sys.stdin

ip=lambda: int(sp())
fp=lambda: float(sp())
lp=lambda:list(map(int,stdin.readline().split()))
sp=lambda:stdin.readline().rstrip()
yp=lambda:print('Yes')
np=lambda:print('No')

n,m=lp()
ans=[100000000 for _ in range(n)]
train=[[] for _ in range(n)]
for _ in range(m):
  p,q,l=lp()
  train[p-1].append([q-1,l])
  train[q-1].append([p-1,l])
  
ans[0]=1
d=train[0]
d=deque(d)
for i in train[0]:
  x,y=i
  ans[x]=1

tra_now=[-1 for _ in range(n)]

while d:
  v,now=d.popleft()
  tra_now[v]=now
  for i in train[v]:
    if ans[i[0]]>ans[v]+1:
      if i[1]==now:
        ans[i[0]]=ans[v]
        d.appendleft([i[0],now])
        
      else:
        ans[i[0]]=ans[v]+1
        d.append([i[0],i[1]])
        
if ans[n-1]==100000000:
  print(-1)
else:
  print(ans[n-1])
  
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
stdin=sys.stdin

ip=lambda: int(sp())
fp=lambda: float(sp())
lp=lambda:list(map(int,stdin.readline().split()))
sp=lambda:stdin.readline().rstrip()
yp=lambda:print('Yes')
np=lambda:print('No')

n,m=lp()
ans=[100000000 for _ in range(n)]
train=[[] for _ in range(n)]
for _ in range(m):
  p,q,l=lp()
  train[p-1].append([q-1,l])
  train[q-1].append([p-1,l])
  
ans[0]=1
d=train[0]
d=deque(d)
for i in train[0]:
  x,y=i
  ans[x]=1

tra_now=[-1 for _ in range(n)]

while d:
  v,now=d.popleft()
  tra_now[v]=now
  for i in train[v]:
    if ans[i[0]]>ans[v]+1:
      if i[1]==now:
        ans[i[0]]=ans[v]
        d.appendleft([i[0],now])
        
      else:
        ans[i[0]]=ans[v]+1
        d.append([i[0],i[1]])
        
if ans[n-1]==100000000:
  print(-1)
else:
  print(ans[n-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict 

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

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

INF = 10**20
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(count)]
for p,q,c in pqc:
  v1,v2 = to1d[p][c],to1d[q][c]
  G[v1][v2] = G[v2][v1] = 0
  
for v in range(N):
  if len(to1d[v])>1:
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1
        
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
  
def bfs01(s):
    from collections import deque
    seen = [0]*len(G)
    d = [INF]*len(G)
    d[s] = 0
    todo = deque()
    seen[s]=1
    todo.append(s)
    while todo:
      a = todo.popleft()
      for b in G[a].keys():
        if seen[b] == 0:
          seen[b] = 1
          if G[a][b]==0:
            todo.appendleft(b)
            d[b] = d[a]
          else:
            todo.append(b)
            d[b] = d[a] + 1
    return d
  
d = bfs01(0)
ans = d[1]
print(ans if ans < INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    p,q,c = map(int,input().split())
    edges[p-1].append((q-1,c))
visited = [False]*N
visited[0] = True
q = deque([(0,None,0)])
while q:
    i, prev, cost = q.popleft()
    if i == N-1:
        print(cost)
        exit()
    for j, nxt in edges[i]:
        if not visited[j]:
            visited[j] = True
            if prev == nxt:
                q.appendleft((j, nxt, cost))
            else:
                q.append((j, nxt, cost+1))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
INF = 10 ** 18
Tree = defaultdict(lambda: [])
for _ in range(M):
    p, q, c = map(int, input().split())
    p -= 1
    q -= 1
    Tree[p].append((q, c))
    Tree[q].append((p, c))

# print(Tree)
dist = [INF] * N


def bfs01(x):
    q = deque([(x, 0)])
    dist[x] = 0
    while q:
        u, rail = q.popleft()
        for nx_node, nx_rail in Tree[u]:
            exchange = rail != nx_rail
            d = dist[u] + int(exchange)
            if d < dist[nx_node]:
                dist[nx_node] = d
                if exchange:
                    q.append((nx_node, nx_rail))
                else:
                    q.appendleft((nx_node, nx_rail))


bfs01(0)
# print(dist)
if dist[N - 1] == INF:
    print(-1)
else:
    print(dist[N - 1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import deque,defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10**31
N,M = map(int,readline().split())
edges = defaultdict(list)
for i in range(M):
    p,q,c = map(int,readline().split())
    edges[(p,c)].append((q,c,0))
    edges[(q,c)].append((p,c,0))
    edges[(p,0)].append((p,c,1))
    edges[(p,c)].append((p,c,0))
    edges[(q,0)].append((q,c,1))
    edges[(q,c)].append((q,0,0))
    
dist = defaultdict(lambda:INF)
q = deque([(1,0)])
dist[(1,0)] = 0

while q:
    x,c_x = q.popleft()
    for y,c_y,cost in edges[(x,c_x)]:
        d = dist[(x,c_x)] + cost
        if d < dist[(y,c_y)]:
            dist[(y,c_y)] = d
            if d == 0:
                q.appendleft((y,c_y))
            else:
                q.append((y,c_y))
ans = dist[(N,0)]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
import collections

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    p, q, c = map(lambda x:int(x) - 1, input().split())
    g[p].append((q, c))
    g[q].append((p, c))

que = collections.deque()
que.append((0, -1, 0))
cost = [float("INF")] * n
cost[0] = 0
seen = [set() for _ in range(n)]

while que:
    ps, pc, pf = que.popleft()
    for ns, nc in g[ps]:
        if pc == nc:
            nf = pf
            if cost[ns] > nf:
                cost[ns] = nf
                que.appendleft((ns, nc, nf))
                seen[ns].add(nc)
            elif cost[ns] == pf - 1 and not nc in seen[ns]:
                que.appendleft((ns, nc, nf))
                seen[ns].add(nc)
        else:
            nf = pf + 1
            if cost[ns] > nf:
                cost[ns] = nf
                que.append((ns, nc, nf))
                seen[ns].add(nc)
            elif cost[ns] == pf - 1 and not nc in seen[ns]:
                que.append((ns, nc, nf))
                seen[ns].add(nc)

if cost[n - 1] == float("INF"):
    print(-1)
else:
    print(cost[n - 1])

Submission status: Wrong Answer

Solution code:
import collections

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    p, q, c = map(lambda x:int(x) - 1, input().split())
    g[p].append((q, c))
    g[q].append((p, c))

que = collections.deque()
que.append((0, -1))
cost = [float("INF")] * n
cost[0] = 0
seen = [set() for _ in range(n)]

while que:
    ps, pc = que.popleft()
    for ns, nc in g[ps]:
        if pc == nc:
          if cost[ns] > cost[ps] or (cost[ns] == cost[ps] and not nc in seen[ns]):
            cost[ns] = cost[ps]
            que.appendleft((ns, nc))
            seen[ns].add(nc)
        elif pc != nc:
          if (cost[ns] > cost[ps] + 1) or (cost[ns] == cost[ps] + 1 and not nc in seen[ns]):
            cost[ns] = cost[ps] + 1
            que.append((ns, nc))
            seen[ns].add(nc)

if cost[n - 1] == float("INF"):
    print(-1)
else:
    print(cost[n - 1])

Submission status: Wrong Answer

Solution code:
import collections

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    p, q, c = map(lambda x:int(x) - 1, input().split())
    g[p].append((q, c))
    g[q].append((p, c))

que = collections.deque()
que.append((0, -1))
cost = [float("INF")] * n
cost[0] = 0

while que:
    ps, pc = que.popleft()
    for ns, nc in g[ps]:
        if pc == nc and cost[ns] > cost[ps]:
            cost[ns] = cost[ps]
            que.appendleft((ns, nc))
        elif pc != nc and cost[ns] > cost[ps] + 1:
            cost[ns] = cost[ps] + 1
            que.append((ns, nc))

if cost[n - 1] == float("INF"):
    print(-1)
else:
    print(cost[n - 1])

Submission status: Wrong Answer

Solution code:
import collections

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    p, q, c = map(lambda x:int(x) - 1, input().split())
    g[p].append((q, c))
    g[q].append((p, c))

que = collections.deque()
que.append((0, m))
cost = [float("INF")] * n
cost[0] = 0

while que:
    ps, pc = que.popleft()
    for ns, nc in g[ps]:
        if pc == nc and cost[ns] > cost[ps]:
            cost[ns] = cost[ps]
            que.appendleft((ns, nc))
        elif pc != nc and cost[ns] > cost[ps] + 1:
            cost[ns] = cost[ps] + 1
            que.append((ns, nc))

if cost[n - 1] == float("INF"):
    print(-1)
else:
    print(cost[n - 1])

Submission status: Wrong Answer

Solution code:
import collections

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    p, q, c = map(lambda x:int(x) - 1, input().split())
    g[p].append((q, c))
    g[q].append((p, c))

que = collections.deque()
que.append((0, n))
cost = [float("INF")] * n
cost[0] = 0

while que:
    ps, pc = que.popleft()
    for ns, nc in g[ps]:
        if pc == nc and cost[ns] > cost[ps]:
            cost[ns] = cost[ps]
            que.appendleft((ns, nc))
        elif pc != nc and cost[ns] > cost[ps] + 1:
            cost[ns] = cost[ps] + 1
            que.append((ns, nc))

if cost[n - 1] == float("INF"):
    print(-1)
else:
    print(cost[n - 1])

Submission status: Wrong Answer

Solution code:
from collections import deque
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]

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)
#print(to)
#print(fin)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
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]

inf=10**9
n,m=MI()
to=[]
uctoi={}
fin=[]
# 改札外
for u in range(n):
    to.append([])
    uctoi[u,0]=u
    fin.append(0)

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)
        fin.append(2 if u==n-1 else 0)
        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)
        fin.append(2 if v==n-1 else 0)
        to.append([])
        to[j].append(v)
        to[v].append(j)
    else:j=uctoi[v,c]
    to[i].append(j)
    to[j].append(i)
#print(to)
#print(fin)

q=deque()
q.append((0,0))
fin[0]=1
while q:
    d,i=q.popleft()
    if i<n:
        for j in to[i]:
            if fin[j]:continue
            fin[j]=1
            q.append((d+1,j))
    else:
        for j in to[i]:
            if fin[j]==2:
                print(d)
                exit()
            if fin[j]:continue
            fin[j]=1
            q.appendleft((d,j))
print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
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]

n,m=MI()
to=[[] for _ in range(n)]
inf=10**9
for _ in range(m):
    u,v,c=MI1()
    to[u].append((v,c))
    to[v].append((u,c))
hp=[]
dist=[inf]*n
home=[set() for _ in range(n)]

dist[0]=0
for v,c in to[0]:
    heappush(hp,(1,v,c))
    dist[v]=1
    home[v].add(c)
    home[0].add(c)

while hp:
    d,u,c=heappop(hp)
    if u==n-1:
        print(d)
        break
    if d>dist[u]:continue
    for v,nc in to[u]:
        nd=d if nc==c else d+1
        if nd>dist[v] or nc in home[v]:continue
        dist[v]=nd
        home[v].add(nc)
        heappush(hp,(nd,v,nc))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
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]

n,m=MI()
to=[[] for _ in range(n)]
inf=10**6
for _ in range(m):
    u,v,c=MI1()
    to[u].append((v,c))
    to[v].append((u,c))
hp=[]
dist=[inf]*n
home=[set() for _ in range(n)]

dist[0]=0
for v,c in to[0]:
    heappush(hp,(1,v,c))
    dist[v]=1
    home[v].add(c)

while hp:
    d,u,c=heappop(hp)
    if u==n-1:
        print(d)
        break
    if d>dist[u]:continue
    for v,nc in to[u]:
        nd=d if nc==c else d+1
        if nd>dist[v] or nc in home[v]:continue
        dist[v]=nd
        home[v].add(nc)
        heappush(hp,(nd,v,nc))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
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]

n,m=MI()
to=[[] for _ in range(n)]
inf=10**6
for _ in range(m):
    u,v,c=MI1()
    to[u].append((v,c))
    to[v].append((u,c))
hp=[]
dd=[inf]*n
heappush(hp,(0,0,-1))
dd[0]=0
while hp:
    d,u,c=heappop(hp)
    if u==n-1:
        print(d)
        break
    if dd[u]<d:continue
    for v,nc in to[u]:
        nd=d if c==nc else d+1
        if dd[v]<=nd:continue
        dd[v]=nd
        heappush(hp,(nd,v,nc))
else:
    print(-1)

Submission status: Wrong Answer

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


class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)


def bfs():
    dp[sup_v][0] = 1
    q = deque([(sup_v, 0)])
    while q:
        v1, v2 = q.popleft()
        for nxt_v1, nxt_v2, cost in graph[v1][v2]:
            if dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q.appendleft((nxt_v1, nxt_v2))
                else:
                    q.append((nxt_v1, nxt_v2))

n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
INF = 10 ** 18


uf = UnionFind(n)
sup_v = 10 ** 6
graph = {sup_v: {}}
dp = {sup_v: {}}
for a, b, c in info:
    a -= 1
    b -= 1
    if c not in graph:
        graph[c] = {}
        dp[c] = {}
    if a not in graph[c]:
        graph[c][a] = []
        graph[c][a].append((sup_v, a, 1))
        dp[c][a] = INF
    if b not in graph[c]:
        graph[c][b] = []
        graph[c][b].append((sup_v, b, 1))
        dp[c][b] = INF
    if a not in graph[sup_v]:
        graph[sup_v][a] = []
        dp[sup_v][a] = INF
    if b not in graph[sup_v]:
        graph[sup_v][b] = []
        dp[sup_v][b] = INF

    graph[c][a].append((c, b, 0))
    graph[c][b].append((c, a, 0))
    graph[sup_v][a].append((c, b, 0))
    graph[sup_v][b].append((c, a, 0))
    
    uf.merge(a, b)
    
if not uf.is_same(0, n - 1):
    print(-1)
    exit()
    

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

Submission status: Wrong Answer

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


class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)


def dijkstra():
    dp[sup_v][0] = 1
    q = [(0, sup_v, 0)] # q = [(startからの距離, 現在地)]
    while q:
        d, v1, v2 = heapq.heappop(q)
        if dp[v1][v2] < d:
            continue
        for nxt_v1, nxt_v2, cost in graph[v1][v2]:
            if dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                heapq.heappush(q, (dp[nxt_v1][nxt_v2], nxt_v1, nxt_v2))


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
INF = 10 ** 18


uf = UnionFind(n)
sup_v = 10 ** 6
graph = {sup_v: {}}
dp = {sup_v: {}}
for a, b, c in info:
    a -= 1
    b -= 1
    if c not in graph:
        graph[c] = {}
        dp[c] = {}
    if a not in graph[c]:
        graph[c][a] = []
        graph[c][a].append((sup_v, a, 1))
        dp[c][a] = INF
    if b not in graph[c]:
        graph[c][b] = []
        graph[c][b].append((sup_v, b, 1))
        dp[c][b] = INF
    if a not in graph[sup_v]:
        graph[sup_v][a] = []
        dp[sup_v][a] = INF
    if b not in graph[sup_v]:
        graph[sup_v][b] = []
        dp[sup_v][b] = INF

    graph[c][a].append((c, b, 0))
    graph[c][b].append((c, a, 0))
    graph[sup_v][a].append((c, b, 0))
    graph[sup_v][b].append((c, a, 0))
    
    uf.merge(a, b)
    
if not uf.is_same(0, n - 1):
    print(-1)
    exit()
    

dijkstra()
ans = INF
for i in dp:
    for j in dp[i]:
        if j == n - 1:
            ans = min(dp[i][j], ans)            
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
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])
res = {0:0}

mask = (1<<20)-1
INF = 1<<29
while q:
    vldv = q.popleft()
    vl,dv = vldv>>20, vldv&mask
    if res[vl] < dv: continue
    if vl==(n-1)<<20: 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.appendleft((tl<<20)+ndv)
            else:
                q.append((tl<<20)+ndv)
            

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
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
INF = 1<<30
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.appendleft((tl,ndv))
            else:
                q.append((tl,ndv))
            

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

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

g = [[] for _ in range(n)]
M = iter(pqc)

#s = [set() for _ in range(n)]
s = set()
for p,q,c in zip(M,M,M):
    p -= 1
    q -= 1
    g[p].append((q,c))
    g[q].append((p,c))
    if p==0 or q==0: s.add(c)
    #s[p].add(c)
    #s[q].add(c)
    


from collections import deque
def bfs01(g,s):
    n = len(g)
    #checked = [0]*n
    #checked[0] = 1
    ans = INF = 1<<30
    
    q = deque((0,ci,1) for ci in s)
    res = {(0,ci):1 for ci in s}
    #print(res)
    while q:
        v,l,dv = q.popleft()
        if res[(v,l)] < dv: continue
        for to,line in g[v]:
            tl = (to,line)
            ndv = dv+(not l==line)
            if tl not in res or res[tl] > ndv:
                res[tl] = ndv
                if l==line: q.appendleft((to,line,ndv))
                else: q.append((to,line,ndv))
                
                if to == n-1: ans = min(ans,ndv)
                
                #print(tl,ndv,(v,l,dv),l==line)
                
        #print(q)

    return ans



print(bfs01(g,s))


#print(res)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    D = dict()
    for _ in range(M):
        p, q, c = map(int, input().split())
        Edge[p-1].append((q-1, c))
        Edge[q-1].append((p-1, c))
        D[(p-1, c)] = D[(q-1, c)] = -1
    for i in range(N): D[(i, -1)] = -1
    q = []
    heappush(q, (0, 0, -1)) #cost, node, company, switch

    while q:
        d, nn, nc = heappop(q)
        if D[(nn, nc)] == -1:
            D[(nn, nc)] = d
            if nc == -1:
                for ne, c in Edge[nn]:
                    if D[(ne, c)] == -1: heappush(q, (d+1, ne, c))
            else:
                heappush(q, (d, nn, -1))
                for ne, c in Edge[nn]:
                    if c == nc and D[(ne, c)] == 10 ** 10: heappush(q, (d, ne, c))
    
    print(D[(N-1, -1)])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        Edge[p-1].append((q-1, c))
        Edge[q-1].append((p-1, c))
    q = []
    Dist = [[10 ** 20 for _ in range(N)] for _ in range(2)]
    heappush(q, (0, 0, -1, 0)) #cost, node, company, switch

    while q:
        d, nn, nc, s = heappop(q)
        if Dist[s][nn] == 10 ** 20:
            Dist[s][nn] = d
            if s == 1:
                for ne, c in Edge[nn]:
                    if Dist[0][ne] == 10 ** 20: heappush(q, (d + 1, ne, c, 0))
            else:
                heappush(q, (d, nn, nc, 1))
                for ne, c in Edge[nn]:
                    if c == nc and Dist[0][ne] == 10 ** 20: heappush(q, (d, ne, c, 0))

    if Dist[0][N-1] == Dist[1][N-1] == 10 ** 20: 
        print(-1)
    else: 
        print(min(Dist[0][N-1], Dist[1][N-1]))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        Edge[p-1].append((q-1, c))
        Edge[q-1].append((p-1, c))
    q = []
    Dist = [[10 ** 20 for _ in range(N)] for _ in range(2)]
    Dist[0][0] = 0
    for ne, c in Edge[0]: heappush(q, (1, ne, c, 1)) #cost, node, company, switch

    while q:
        d, nn, nc, s = heappop(q)
        if Dist[s][nn] == 10 ** 20:
            Dist[s][nn] = d
            if s == 1:
                for ne, c in Edge[nn]:
                    if Dist[0][ne] == 10 ** 20: heappush(q, (d + 1, ne, c, 0))
            else:
                heappush(q, (d, nn, nc, 1))
                for ne, c in Edge[nn]:
                    if c == nc and Dist[0][ne] == 10 ** 20: heappush(q, (d, ne, c, 0))

    if Dist[0][N-1] == Dist[1][N-1] == 10 ** 20: 
        print(-1)
    else: 
        print(min(Dist[0][N-1], Dist[1][N-1]))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        Edge[p-1].append((q-1, c))
        Edge[q-1].append((p-1, c))
    q = []
    Dist = [[10 ** 20 for _ in range(N)] for _ in range(2)]
    Dist[0][0] = 0
    for ne, c in Edge[0]: heappush(q, (1, ne, c, 0)) #cost, node, company, switch

    while q:
        d, nn, nc, s = heappop(q)
        if Dist[s][nn] == 10 ** 20:
            Dist[s][nn] = d
            for ne, c in Edge[nn]:
                if c == nc and Dist[s][ne] == 10 ** 20: heappush(q, (d, ne, c, s))
                elif c != nc and Dist[s][ne] == 10 ** 20: heappush(q, (d+1, ne, c, s^1))

    if Dist[0][N-1] == Dist[1][N-1] == 10 ** 20: 
        print(-1)
    else: 
        print(min(Dist[0][N-1], Dist[1][N-1]))

    return 0

if __name__ == "__main__":
    solve()