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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

n,m=LI()
g=[[] for i in range(n)]

for i in range(m):
    p,q,r=LI_()
    g[p].append((q,r))
    g[q].append((p,r))

def bfs01(g,x):
    d=[(0 if i==x else inf) for i in range(n)]
    q=deque()
    q.append((x,-1))
    while q:
        cs,cr=q.popleft()
        for nx,r in g[cs]:
            fee=0 if r==cr else 1
            alt=d[cs]+ fee
            if alt<d[nx]:
                d[nx]=alt
                if fee==0:
                    q.appendleft((nx,r))
                else:
                    q.append((nx,r))
    return d

d=bfs01(g,0)

ans=d[-1]
if ans==inf:
    ans=-1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[[]for i in range(n+1)]
for j in range(m):
    p,q,c=map(int,input().split())
    s[p].append([q,c])
    s[q].append([p,c])
l=[-1]*(n+1)
l[1]=0
d=[[1,0,0]]
while not l[-1] or d:
    a,b,c=d.pop(0)
    for i,j in s[a]:
        if l[i]==-1:
            if j==b:
                l[i]=c
                d.insert(0,[i,b,c])
            else:
                l[i]=c+1
                d.append([i,j,c+1])
print(l[-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
R = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  R[p].append((q, c))
  R[q].append((p, c))
seen = [False]*n
dq = deque()
dq.append((0, 0, -1))
while dq:
  v, cost, company = dq.popleft()
  seen[v] = True
  if v == n-1:
    print(cost)
    break
  for nv, ncom in R[v]:
    if seen[nv]:
      continue
    if ncom == company:
      dq.appendleft((nv, cost, ncom))
    else:
      dq.append((nv, cost+1, ncom))
else:
  print(-1)

Submission status: Wrong Answer

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,0) for p in range(1,N+1)]
V += [(p,c) for p,c in zip(P,C)]
V += [(q,c) for q,c in zip(Q,C)]
V = set(V)
label = {x:i for i,x in enumerate(V)}
start = label[(1,0)]
goal = label[(N,0)]

N = len(V)
graph = [[] for _ in range(N)]
for p,q,c in zip(P,Q,C):
    v0 = label[(p,0)]; v1 = label[(p,c)]
    w0 = label[(q,0)]; w1 = label[(q,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([(0,start)])
while q:
    dv,v = q.popleft()
    for w,cost in graph[v]:
        dw = dv + cost
        if dw >= dist[w]:
            continue
        dist[w] = dw
        if not cost:
            q.appendleft((dw,w))
        else:
            q.append((dw,w))

answer = dist[goal]
print(answer)

Submission status: Wrong Answer

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,0) for p in range(1,N+1)]
V += [(p,c) for p,c in zip(P,C)]
V += [(q,c) for q,c in zip(Q,C)]
V = set(V)
label = {x:i for i,x in enumerate(V)}
start = label[(1,0)]
goal = label[(N,0)]

N = len(V)
graph = [[] for _ in range(N)]
for p,q,c in zip(P,Q,C):
    v0 = label[(p,0)]; v1 = label[(p,c)]
    w0 = label[(q,0)]; w1 = label[(q,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([(0,start)])
while q:
    dv,v = q.popleft()
    for w,cost in graph[v]:
        dw = dv + cost
        if dw >= dist[w]:
            continue
        dist[w] = dw
        if not cost:
            q.appendleft((dw,w))
        else:
            q.append((dw,w))

answer = dist[goal]
print(answer)

dist

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N+10**6)]
for _ in range(M):
    p, q, c = map(int, input().split())
    G[p-1].append(N+c-1)
    G[q-1].append(N+c-1)
    G[N+c-1].append(p-1)
    G[N+c-1].append(q-1)
dist = [-1]*(N+10**6)
que = deque([0])
dist[0] = 0
while que:
    v = que.pop()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]<0:
            dist[nv] = d+1
            que.append(nv)
print(dist[N-1]//2)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [defaultdict(int) for _ in range(N+1)]
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        if c in prev[v] and seen[u][c] == 0:
            if cost[u] == cost[v]:
                prev[u].append(c)
            elif cost[u] > cost[v]:
                cost[u] = cost[v]
                deq.append(u)
                prev[u] = [c]
            seen[v][c] = 1
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                deq.appendleft(u)
                prev[u] = [c]
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [0] * (N+1)
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
while deq:
    v = deq.pop()
    if seen[v] == 1:
        continue
    else:
        seen[v] = 1
    for uc in adj[v]:
        u, c = uc
        if c in prev[v]:
            if cost[u] == cost[v]:
                prev[u].append(c)
            elif cost[u] > cost[v]:
                cost[u] = cost[v]
                deq.append(u)
                prev[u] = [c]
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                deq.appendleft(u)
                prev[u] = [c]
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [defaultdict(int) for _ in range(N+1)]
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        if seen[u][c] == 1:
            continue
        else:
            seen[u][c] = 1
        if c in prev[v]:
            if cost[u] == cost[v]:
                prev[u].append(c)
            elif cost[u] > cost[v]:
                cost[u] = cost[v]
                deq.append(u)
                prev[u] = [c]
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                deq.appendleft(u)
                prev[u].append(c)
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [0] * (N+1)
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
while deq:
    v = deq.pop()
    if seen[v] == 1:
        continue
    else:
        seen[v] = 1
    for uc in adj[v]:
        u, c = uc
        if c in prev[v]:
            if cost[u] == cost[v]:
                prev[u].append(c)
            elif cost[u] > cost[v]:
                cost[u] = cost[v]
                deq.append(u)
                prev[u] = [c]
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                deq.appendleft(u)
                prev[u].append(c)
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [0] * (N+1)
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
seen[1] = 1
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        if c in prev[v]:
            if cost[u] == cost[v]:
                cost[u] = cost[v]
                if seen[u] == 0:
                    deq.append(u)
                    seen[u] = 1
                prev[u].append(c)
            elif cost[u] > cost[v]:
                cost[u] = cost[v]
                if seen[u] == 0:
                    deq.append(u)
                    seen[u] = 1
                prev[u] = [c]
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                if seen[u] == 0:
                    deq.appendleft(u)
                    seen[u] = 1
                prev[u].append(c)
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [0] * (N+1)
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
seen[1] = 1
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        if c in prev[v]:
            if cost[u] >= cost[v]:
                cost[u] = cost[v]
                if seen[u] == 0:
                    deq.append(u)
                    seen[u] = 1
                prev[u].append(c)
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                deq.appendleft(u)
                seen[u] = 1
                prev[u].append(c)
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [0] * (N+1)
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        if c in prev[v]:
            if cost[u] >= cost[v]:
                if seen[u] == 0:
                    cost[u] = cost[v]
                    deq.append(u)
                    prev[u].append(c)
                    seen[v] = 1
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                deq.appendleft(u)
                prev[u].append(c)
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
seen = [10 ** 7] * (N+1)
prev = defaultdict(list)
deq.append(1)
seen[1] = 0
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        if c in prev[v]:
            if seen[u] > seen[v]:
                seen[u] = seen[v]
                deq.append(u)
                prev[u].append(c)
        else:
            if seen[u] > seen[v] + 1:
                seen[u] = seen[v] + 1
                deq.appendleft(u)
                prev[u].append(c)
            elif seen[u] == seen[v] + 1:
                prev[u].append(c)

print(seen[N]) if seen[N] < 10 ** 7 else print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
seen = [10 ** 7] * (N+1)
prev = defaultdict(list)
deq.append(1)
seen[1] = 0
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        if c in prev[v]:
            if seen[u] > seen[v]:
                seen[u] = seen[v]
                deq.append(u)
                prev[u].append(c)
        else:
            if seen[u] > seen[v] + 1:
                seen[u] = seen[v] + 1
                deq.appendleft(u)
                prev[u].append(c)
            elif seen[u] == seen[v] + 1:
                prev[u].append(c)

print(seen[N])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = {k: [] for k in range(N+1)}
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].append((q, c))
    G[q].append((p, c))


dist = [10**11 for _ in range(N+1)]
dist[1] = 0

cpny = [set() for _ in range(N+1)]

que = deque([(1, -1, 0)])

while que:
    ci, cc, d = que.popleft()
    cpny[ci].add(cc)

    for ni, nc in G[ci]:
        if cc == nc and dist[ni] > d:
            dist[ni] = d
            que.appendleft((ni, nc, d))
        elif cc != nc and dist[ni] > d+1:
            dist[ni] = d+1
            que.append((ni, nc, d+1))
        elif cc != nc and dist[ni] == d+1 and nc not in cpny[ni]:
            dist[ni] = d+1
            que.append((ni, nc, d+1))

if dist[N] < 10**11:
    print(dist[N])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = {k: [] for k in range(N+1)}
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].append((q, c))
    G[q].append((p, c))


dist = [10**11 for _ in range(N+1)]
dist[1] = 0

cpny = [set() for _ in range(N+1)]

que = deque([(1, -1, 0)])

while que:
    ci, cc, d = que.popleft()
    cpny[ci].add(cc)

    for ni, nc in G[ci]:
        if cc == nc and dist[ni] >= d and nc not in cpny[ni]:
            dist[ni] = d
            que.appendleft((ni, nc, d))
        elif cc != nc and dist[ni] > d+1:
            dist[ni] = d+1
            que.append((ni, nc, d+1))

if dist[N] < 10**11:
    print(dist[N])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = {k: [] for k in range(N+1)}
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].append((q, c))
    G[q].append((p, c))


dist = [10**13 for _ in range(N+1)]
dist[1] = 0

que = deque([(1, -1, 0, -1)])

while que:
    ci, cc, d, p = que.popleft()

    for ni, nc in G[ci]:
        if cc == nc and dist[ni] >= d and ni != p:
            dist[ni] = d
            que.appendleft((ni, nc, d, ci))
        elif cc != nc and dist[ni] > d+1:
            dist[ni] = d+1
            que.append((ni, nc, d+1, ci))

if dist[N] < 10**13:
    print(dist[N])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = {k: [] for k in range(N+1)}
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].append((q, c))
    G[q].append((p, c))


dist = [10**13 for _ in range(N+1)]
dist[1] = 0

que = deque([(1, -1, 0)])

while que:
    ci, cc, d = que.popleft()

    for ni, nc in G[ci]:
        if cc == nc and dist[ni] > d:
            dist[ni] = d
            que.appendleft((ni, nc, d))
        elif cc != nc and dist[ni] > d+1:
            dist[ni] = d+1
            que.append((ni, nc, d+1))

if dist[N] < 10**13:
    print(dist[N])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

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

G = {k: [] for k in range(N+1)}
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].append((q, c))
    G[q].append((p, c))


dist = [10**13 for _ in range(N+1)]
dist[1] = 0

que = deque([(1, -1, 0)])

while que:
    ci, cc, d = que.popleft()

    for ni, nc in G[ci]:
        if cc == nc and dist[ni] > d:
            dist[ni] = d
            que.appendleft((ni, nc, d))
        elif cc != nc and dist[ni] > d+1:
            dist[ni] = d+1
            que.append((ni, nc, d+1))

if dist[N] < 10**11:
    print(dist[N])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

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

G = {k: [] for k in range(N+1)}
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].append((q, c))
    G[q].append((p, c))


dist = [10**11 for _ in range(N+1)]
dist[1] = 0

que = deque([(1, -1, 0)])

while que:
    ci, cc, d = que.popleft()

    for ni, nc in G[ci]:
        if cc == nc and dist[ni] > d:
            dist[ni] = d
            que.appendleft((ni, nc, d))
        elif cc != nc and dist[ni] > d+1:
            dist[ni] = d+1
            que.append((ni, nc, d+1))

if dist[N] < 10**11:
    print(dist[N])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

inf = float('inf')
input = sys.stdin.readline

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

adj = [set() for _ in range(n)]
trs = [set() for _ in range(n)]

for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1
    q -= 1
    adj[p].add((q, c))
    adj[q].add((p, c))
    trs[p].add(c)
    trs[q].add(c)

dq = deque()
for c in trs[0]:
    dq.append((0, c, 0))

costs = [inf] * n
while dq:
    cur_st, cur_com, cur_cost = dq.popleft()
    costs[cur_st] = cur_cost

    for nxt_st, nxt_com in adj[cur_st]:
        if nxt_com != cur_com:
            if costs[nxt_st] > cur_cost + 1:
                dq.append((nxt_st, nxt_com, cur_cost + 1))
        else:
            if costs[nxt_st] > cur_cost:
                dq.appendleft((nxt_st, nxt_com, cur_cost))

if costs[n - 1] == inf:
    print(-1)
else:
    print(costs[n - 1])

Submission status: Wrong Answer

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

from heapq import heappush, heappop

def main():
  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))
    edges[q-1].append((p-1, c))

  cost = [(float('inf'), -1) for i in range(n)]  # costと会社
  visited = [False for _ in range(n)]
  cost[0] = (0, 0)
  h = [(0, 0)]  # costとノード
  while h:
    c, s = heappop(h)
    visited[s] = True
    for t, _c in edges[s]:
      if not visited[t]:
        cc = 1 if cost[s][1] != _c else 0  # 乗り換えがあるか
        if cost[t][0] > cost[s][0] + cc:
          cost[t] = (cost[s][0] + cc, _c)
          heappush(h, (cost[s][0] + cc, t))

  if cost[n-1][0] == float('inf'):
    print(-1)
  else:
    print(cost[n-1][0])


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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


dic = defaultdict(list)
n, m = map(int, input().split())

for _ in range(m):
    p, q, c = map(int, input().split())
    dic[p].append([q, c])
    dic[q].append([p, c])

arrived = [-1] * (n+1)
arrived[1] = 0
todo = deque([[1, 0, 0]])

while todo:
    now, cop, cost = todo.popleft()

    for to, n_cop in dic[now]:
        if arrived[to] >= 0:
            continue

        if n_cop == cop:
            todo.appendleft([to, n_cop, cost])
            arrived[to] = cost
        else:
            todo.append([to, n_cop, cost+1])
            arrived[to] = cost+1

print(arrived[n])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque

dic = defaultdict(list)
n, m = map(int, input().split())

for _ in range(m):
    p, q, c = map(int, input().split())
    dic[p].append([q, c])
    dic[q].append([p, c])

arrived = [-1] * (n+1)
todo = deque([[1, 0, 0]])

while todo:
    now, cop, cost = todo.popleft()
    if arrived[now] != -1:
        continue        
    arrived[now] = cost

    if now == n:
        break

    for to, n_cop in dic[now]:
        if arrived[to] >= 0:
            continue

        if n_cop == cop:
            todo.appendleft([to, n_cop, cost])
        else:
            todo.append([to, n_cop, cost+1])

print(arrived[n])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque

dic = defaultdict(list)
n, m = map(int, input().split())

for _ in range(m):
    p, q, c = map(int, input().split())
    dic[p].append([q, c])
    dic[q].append([p, c])

arrived = [-1] * (n+1)
todo = deque([[1, 0, 0]])
pre = 0

while todo:
    now, cop, cost = todo.popleft()
    arrived[now] = cost

    if now == n:
        break

    for to, n_cop in dic[now]:
        if arrived[to] >= 0:
            continue

        if n_cop == cop:
            todo.appendleft([to, n_cop, cost])
        else:
            todo.append([to, n_cop, cost+1])

print(arrived[n])

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    p, q, c = map(int, input().split())
    p, q, c = p-1, q-1, c-1
    edges[p].append((q, c))
    edges[q].append((p, c))

que = deque()
cost = [float("inf")]*n
# now, prev,prev_color, cost
que.append((0, -1, -1, 0))

while que:
    now, prev, prev_color, cost_now = que.popleft()
    if cost[now] < cost_now:
        continue
    cost[now] = cost_now
    for to, color in edges[now]:
        if to == prev:
            continue
        if cost_now+int(color!=prev_color) < cost[to]:
            que.append((to, now, color, cost_now+int(color!=prev_color)))
if cost[-1] == float("inf"):
    print(-1)
else:
    print(cost[-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    p, q, c = map(int, input().split())
    p, q, c = p-1, q-1, c-1
    edges[p].append((q, c))
    edges[q].append((p, c))

que = deque()
cost = [float("inf")]*n
# now, prev,prev_color, cost
que.append((0, -1, -1, 0))

while que:
    now, prev, prev_color, cost_now = que.popleft()
    if cost[now] <= cost_now:
        continue
    cost[now] = cost_now
    for to, color in edges[now]:
        if to == prev:
            continue
        # 一応ここでフィルタ
        if cost_now+int(color!=prev_color) < cost[to]:
            que.append((to, now, color, cost_now+int(color!=prev_color)))
if cost[-1] == float("inf"):
    print(-1)
else:
    print(cost[-1])

Submission status: Wrong Answer

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:
        x = q.pop()
        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
        continue
    q = q1
    q1 = []
    d += 1

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

N,M = map(int,input().split())
PQC = [[int(x) for x in input().split()] for _ in range(M)]

V = set((x,0) for x in range(1,N+1))
V |= set((p,c) for p,q,c in PQC)
V |= set((q,c) for p,q,c in PQC)
V = list(V)
v_to_i = {v:i for i,v in enumerate(V)}

# グラフを作成
rows, cols = [],[]
rows += [i for i,(p,c) in enumerate(V) if c != 0]
cols += [v_to_i[(p,0)] for i,(p,c) in enumerate(V) if c != 0]
wt = [1] * len(rows)
rows += [v_to_i[(p,c)] for p,q,c in PQC]
cols += [v_to_i[(q,c)] for p,q,c in PQC]
wt += [0] * M

graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))

start = v_to_i[(1,0)]
goal = v_to_i[(N,0)]

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

N,M = map(int,input().split())
PQC = [[int(x) for x in input().split()] for _ in range(M)]

V = set((x,0) for x in range(1,N+1))
V |= set((p,c) for p,q,c in PQC)
V |= set((q,c) for p,q,c in PQC)
V = list(V)
v_to_i = {v:i for i,v in enumerate(V)}

# グラフを作成
rows = []
cols = []
wt = []
for i,(p,c) in enumerate(V):
    if c != 0:
        j = v_to_i[(p,0)]
        rows.append(i)
        cols.append(j)
        wt.append(1)
for p,q,c in PQC:
    i = v_to_i[(p,c)]
    j = v_to_i[(q,c)]
    rows.append(i)
    cols.append(j)
    wt.append(0)

graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))

start = v_to_i[(1,0)]
goal = v_to_i[(N,0)]