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:
import heapq
N,M=map(int,input().split())
G=[dict() for i in range(N)]
C=set()
for i in range(M):
    p,q,c=map(int,input().split())
    G[p-1][q-1]=c
    G[q-1][p-1]=c
    C.add(c)
q=[]
distance=[dict() for i in range(N)]
distance[0][-1]=0
heapq.heappush(q,(0,0,-1))
def dist(a,b):
    if b in distance[a]:
        return distance[a][b]
    else:
        return 10**11
def ans(a,b):
    if b in distance[a]:
        return distance[a][b]
    else:
        return -1
    
while(len(q)>0):
    d,r,c=heapq.heappop(q)
    if dist(r,c)<d:
        continue
    for p in G[r]:
        if G[r][p]==c:
            cost=0
            if dist(p,c)>dist(r,c)+cost:
                distance[p][c]=dist(r,c)+cost
                heapq.heappush(q,(dist(p,c),p,c))
    if c==-1:
        for a in C:
            cost=1
            if dist(r,a)>dist(r,c)+cost:
                distance[r][a]=dist(r,c)+cost
                heapq.heappush(q,(dist(r,a),r,a))
    else:
        cost=0
        if dist(r,-1)>dist(r,c)+cost:
            distance[r][-1]=dist(r,c)+cost
            heapq.heappush(q,(dist(r,-1),r,-1))
print(ans(N-1,-1))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import heapq

INF = 10 ** 9 + 7

def solve(n, m, lst):

    g = {}
    l = [[] for _ in range(n)]
    for p, q, c in lst:
        if not c in g:
            gc = [[] for _ in range(n)]
            g[c] = gc
        else:
            gc = g[c]
        gc[p].append(q)
        gc[q].append(p)
        l[p].append(c)
        l[q].append(c)

    dist = [INF] * n
    dist[0] = 0
    que = []
    heapq.heappush(que, (0, (0, -1)))
    while que:
        d, x = heapq.heappop(que)
        v, c = x
        if c < 0:
            for cv in l[v]:
                heapq.heappush(que, (d + 1, (v, cv)))
        else:
            for w in g[c][v]:
                if d < dist[w]:
                    dist[w] = d
                    heapq.heappush(que, (d, (w, c)))
                    heapq.heappush(que, (d, (w, -1)))

    if dist[-1] == INF:
        return -1

    return dist[-1]


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

    print(solve(n, m, lst))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N,M = list(map(int, input().split()))
PQC = [list(map(int, input().split())) for _ in range(M)]

stations_of_rosen_d = {}
rosens_of_station_l = [set() for _ in range(N+1)] # stations[i]: 駅i

for p,q,c in PQC:
  stations_of_rosen_d.setdefault(c,set()).add(p)
  stations_of_rosen_d[c].add(q)
  rosens_of_station_l[p].add(c)
  rosens_of_station_l[q].add(c)

#print(stations_of_rosen_d)
#print(rosens_of_station_l)
  
visited_stations = set()
visited_rosens = set()

from collections import deque
stack = [1]
ans = -1

while stack:
  ans += 1
  next_stack_l = []
  for s in stack:
    if s==N:
      print(ans)
      break
    if s in visited_stations:
      continue
    else:
      visited_stations.add(s)
      for r in rosens_of_station_l[s]:
        if r in visited_rosens:
          continue
        else:
          visited_rosens.add(r)
          next_stack_l.append(stations_of_rosen_d[r])
  else:
    stack = set().union(*next_stack_l)
    #print(visited_stations)
    #print(visited_rosens)
    #print(stack)
    continue
  break
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
def main():
  from heapq import heappush,heappop,heapify
  inf=10**18
  n,m,*t=map(int,open(0).read().split())
  if not t:
    print(-1)
    exit()
  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)))}
  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)
      d[y]=inf
    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)
  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: Wrong Answer

Solution code:
def main():
  from heapq import heappush,heappop,heapify
  inf=10**12
  n,m,*t=map(int,open(0).read().split())
  if not t:
    print(-1)
    exit()
  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)))}
  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)
      d[y]=inf
    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)
  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: Wrong Answer

Solution code:
def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  if not t:
    print(-1)
    exit()
  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)))}
  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)
      d[y]=inf
    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)
  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: Wrong Answer

Solution code:
from collections import*
from heapq import*
def dijkstra(s):
  d=[inf]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  return d
inf=10**18
n,m,*t=map(int,open(0).read().split())
e=defaultdict(list)
s=[]
l=[]
f=False
for a,b,c in zip(t[::3],t[1::3],t[2::3]):
  if b<a:a,b=b,a
  if a<2 or b<2:f=True
  x,y=a+-~n*c,b+-~n*c
  if b==n:l.append(y)
  e[a].append((1,x))
  e[b].append((1,y))
  e[x].extend([(0,a),(0,y)])
  e[y].extend([(0,b),(0,x)])
  s.extend([a,b,x,y])
if not f:
  print(-1)
  exit()
d={i:v for v,i in enumerate(sorted(set(s)))}
n=len(d)
edge=tuple([]for _ in range(n))
for i in e:
  edge[d[i]].extend([(c,d[j])for c,j in e[i]])
a=dijkstra(0)
#a=min(a[d[i]]for i in l)
#print([a,-1][a==inf])

Submission status: Wrong Answer

Solution code:
from collections import*
from heapq import*
"""
def dijkstra(s):
  d=[inf]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  return d
"""
inf=10**18
n,m,*t=map(int,open(0).read().split())
e=defaultdict(list)
s=[]
l=[]
f=False
for a,b,c in zip(t[::3],t[1::3],t[2::3]):
  if b<a:a,b=b,a
  if a<2 or b<2:f=True
  x,y=a+-~n*c,b+-~n*c
  if b==n:l.append(y)
  e[a].append((1,x))
  e[b].append((1,y))
  e[x].extend([(0,a),(0,y)])
  e[y].extend([(0,b),(0,x)])
  s.extend([a,b,x,y])
if not f:
  print(-1)
  exit()
d={i:v for v,i in enumerate(sorted(set(s)))}
n=len(d)
edge=tuple([]for _ in range(n))
for i in e:
  edge[d[i]].extend([(c,d[j])for c,j in e[i]])
"""
a=dijkstra(0)
a=min(a[d[i]]for i in l)
print([a,-1][a==inf])
"""

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
N, M = map(int, input().split())
Edge = [[] for _ in range(N+1)]
comp = set()
mod = 10**9+7
for _ in range(M):
    p, q, c = map(int, input().split())
    Edge[p].append(mod*q+c)
    Edge[q].append(mod*p+c)
    comp.add(c)
dist = {mod: 0}
Q = deque()
Q.append(mod)
visited = set()
while Q:
    vn, cp = divmod(Q.pop(), mod)
    if mod*vn+cp in visited:
        continue
    if vn == N:
        break
    visited.add(mod*vn+cp)
    for t in Edge[vn]:
        vf, cf = divmod(t, mod)
        if mod*vf+cp in visited:
            continue
        if cp == cf:
            dist[mod*vf+cf] = dist.get(mod*vn+cp, 10**9)
            Q.append(mod*vf+cf)
        else:
            dist[mod*vf+cf] = 1 + dist.get(mod*vn+cp, 10**9)
            Q.appendleft(mod*vf+cf)
L = [dist.get(N*mod+c, 10**9) for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
N, M = map(int, input().split())
Edge = defaultdict(lambda: [])
comp = set()
mod = 10**9+7
for _ in range(M):
    p, q, c = map(int, sys.stdin.readline().split())
    Edge[p].append(mod*q+c)
    Edge[q].append(mod*p+c)
    Edge[mod*p+c].append(mod*q+c)
    Edge[mod*q+c].append(mod*p+c)
    comp.add(c)
dist = defaultdict(lambda: mod)
dist[mod] = 0
Q = deque()
Q.append(mod)
visited = set()
while Q:
    vn, cp = divmod(Q.pop(), mod)
    if mod*vn+cp in visited:
        continue
    if vn == N:
        break
    visited.add(mod*vn+cp)
    pone = False
    for t in Edge[vn*mod+cp]:
        vf, cf = divmod(t, mod)
        if mod*vf+cp in visited:
            continue
        else:
            dist[mod*vf+cf] = min(dist[mod*vf+cf], dist[mod*vn+cp])
            Q.append(mod*vf+cf)
            pone = True
    if not pone:
        for t in Edge[vn]:
            vf, cf = divmod(t, mod)
            if mod*vf+cp in visited or cp == cf:
                continue
            else:
                dist[mod*vf+cf] = min(dist[mod*vf+cf], 1 + dist[mod*vn+cp])
                Q.appendleft(mod*vf+cf)
L = [dist[N*mod+c] for c in comp]
if not L or min(L) == mod:
    print(-1)
else:
    print(min(L))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
N, M = map(int, input().split())
Edge = defaultdict(lambda: [])
comp = set()
mod = 10**9+7
for _ in range(M):
    p, q, c = map(int, input().split())
    Edge[p].append(mod*q+c)
    Edge[q].append(mod*p+c)
    Edge[mod*p+c].append(mod*q+c)
    Edge[mod*q+c].append(mod*p+c)
    comp.add(c)
dist = {mod: 0}
Q = deque()
Q.append(mod)
visited = set()
while Q:
    vn, cp = divmod(Q.pop(), mod)
    if mod*vn+cp in visited:
        continue
    if vn == N:
        break
    visited.add(mod*vn+cp)
    pone = False
    for t in Edge[vn*mod+cp]:
        vf, cf = divmod(t, mod)
        if mod*vf+cp in visited:
            continue
        else:
            dist[mod*vf+cf] = min(dist.get(mod*vf+cf, 10**9), dist.get(mod*vn+cp, 10**9))
            Q.append(mod*vf+cf)
            pone = True
    if not pone:
        for t in Edge[vn]:
            vf, cf = divmod(t, mod)
            if mod*vf+cp in visited or cp == cf:
                continue
            else:
                dist[mod*vf+cf] = min(dist.get(mod*vf+cf, 10**9), 1 + dist.get(mod*vn+cp, 10**9))
                Q.appendleft(mod*vf+cf)
L = [dist.get(N*mod+c, 10**9) for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
N, M = map(int, input().split())
Edge = [[] for _ in range(N+1)]
comp = set()
mod = 10**9+7
for _ in range(M):
    p, q, c = map(int, sys.stdin.readline().split())
    Edge[p].append(mod*q+c)
    Edge[q].append(mod*p+c)
    comp.add(c)
dist = defaultdict(lambda: mod)
Q = deque()
Q.append(mod)
visited = set()
while Q:
    vn, cp = divmod(Q.pop(), mod)
    if mod*vn+cp in visited:
        continue
    if vn == N:
        break
    visited.add(mod*vn+cp)
    for t in Edge[vn]:
        vf, cf = divmod(t, mod)
        if mod*vf+cp in visited:
            continue
        if cp == cf:
            dist[mod*vf+cf] = min(dist[mod*vf+cf], dist[mod*vn+cp])
            Q.append(mod*vf+cf)
            continue
        dist[mod*vf+cf] = min(dist[mod*vf+cf], dist[mod*vn+cp])
        Q.appendleft(mod*vf+cf)
L = [dist[N*mod+c] for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
N, M = map(int, input().split())
Edge = [[] for _ in range(N+1)]
comp = set()
mod = 10**9+7
for _ in range(M):
    p, q, c = map(int, sys.stdin.readline().split())
    Edge[p].append(mod*p+c)
    Edge[q].append(mod*q+c)
    comp.add(c)
dist = {mod: 0}
Q = deque()
Q.append(mod)
visited = set()
while Q:
    vn, cp = divmod(Q.pop(), mod)
    if mod*vn+cp in visited:
        continue
    if vn == N:
        break
    visited.add(mod*vn+cp)
    for t in Edge[vn]:
        vf, cf = divmod(t, mod)
        if mod*vf+cp in visited:
            continue
        if cp == cf:
            dist[mod*vf+cf] = min(dist.get(mod*vf+cf, 10**9), dist.get(mod*vn+cp, 10**9))
            Q.append(mod*vf+cf)
        else:
            dist[mod*vf+cf] = min(dist.get(mod*vf+cf, 10**9), 1 + dist.get(mod*vn+cp, 10**9))
            Q.appendleft(mod*vf+cf)
L = [dist.get(N*mod+c, 10**9) for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
N, M = map(int, input().split())
Edge = [[] for _ in range(N+1)]
comp = set()
for _ in range(M):
    p, q, c = map(int, sys.stdin.readline().split())
    Edge[p].append(10**5*c + q)
    Edge[q].append(10**5*c + p)
    comp.add(c)
dist = {1: 0}
Q = deque()
Q.append(1)
visited = set()
while Q:
    cp, vn = divmod(Q.pop(), 10**5)
    if cp*10**5 + vn in visited:
        continue
    visited.add(cp*10**5 + vn)
    for j in Edge[vn]:
        cf, vf = divmod(j, 10**5)
        if cp*10**5 + vf in visited:
            continue
        if cp == cf:
            dist[cf*10**5 + vf] = min(dist.get(cf*10**5 + vf, 10**9), dist.get(cp*10**5 + vn, 10**9))
            Q.append(cf*10**5 + vf)
        else:
            dist[cf*10**5 + vf] = min(dist.get(cf*10**5 + vf, 10**9), 1 + dist.get(cp*10**5 + vn, 10**9))
            Q.appendleft(cf*10**5 + vf)
L = [dist.get(c*10**5 + N, 10**9) for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

Submission status: Wrong Answer

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 heapq import heappush, heappop

def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF]*n
    visited = [False]*n
    
    dist[start] = 1
    que = [(dist[start], start)]
    
    while que:
        cost, cur = heappop(que)
        
        if visited[cur]:
            continue
        
        visited[cur] = True
        
        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))
      
    return dist

def get_nodenum(station, company, keyset, node2num):
    if (station, company) not in keyset:
        keyset.add((station, company))
        keyslen = len(keyset)-1
        node2num.update({(station, company): keyslen})
        
        return keyslen
    
    else:
        return node2num[(station, company)]
    

n,m = li()

graph = [[] for _ in range(5*(10**5))]
node2num = {}
num2node = {}
keyset = set()

start = -1

for _ in range(m):
    p,q,c = li()
    
    # pかqが1ならスタートに設定
    
    # ノードの登録
    pc_nodenum = get_nodenum(p,c,keyset,node2num)
    qc_nodenum = get_nodenum(q,c,keyset,node2num)
    
    pz_nodenum = get_nodenum(p,0,keyset,node2num)
    qz_nodenum = get_nodenum(q,0,keyset,node2num)
    
    # pかqが1ならスタートに設定
    if p == 1:
        start = pc_nodenum
    elif q == 1:
        start = qc_nodenum
    
    # 隣接リストの更新
    graph[pc_nodenum].append((qc_nodenum, 0))
    graph[qc_nodenum].append((pc_nodenum, 0))
    
    graph[pc_nodenum].append((pz_nodenum, 0))
    graph[qc_nodenum].append((qz_nodenum, 0))
    
    graph[pz_nodenum].append((pc_nodenum, 1))
    graph[qz_nodenum].append((qc_nodenum, 1))
    
num2node = {ni: (stati, compi) for (stati, compi), ni in node2num.items()}

INF = 1<<62
ans = INF

if start == -1:
    print(-1)

else:
    dist = dijkstra(graph, start, INF)
    for nodei in range(len(keyset)):
        if num2node[nodei][0] == n:
            ans = min(ans, dist[nodei])
            
    print(-1 if ans == INF else ans)

Submission status: Wrong Answer

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 heapq import heappush, heappop

def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF]*n
    visited = [False]*n
    
    dist[start] = 1
    que = [(dist[start], start)]
    
    while que:
        cost, cur = heappop(que)
        
        if visited[cur]:
            continue
        
        visited[cur] = True
        
        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))
      
    return dist

def get_nodenum(station, company, keyset, node2num):
    if (station, company) not in keyset:
        keyset.add((station, company))
        keyslen = len(keyset)-1
        node2num.update({(station, company): keyslen})
        
        return keyslen
    
    else:
        return node2num[(station, company)]
    

n,m = li()

graph = [[] for _ in range(5*(10**5))]
node2num = {}
num2node = {}
keyset = set()

start = -1

for _ in range(m):
    p,q,c = li()
    
    # pかqが1ならスタートに設定
    
    # ノードの登録
    pc_nodenum = get_nodenum(p,c,keyset,node2num)
    qc_nodenum = get_nodenum(q,c,keyset,node2num)
    
    pz_nodenum = get_nodenum(p,0,keyset,node2num)
    qz_nodenum = get_nodenum(q,0,keyset,node2num)
    
    # pかqが1ならスタートに設定
    if p == 1:
        start = pc_nodenum
    elif q == 1:
        start = qc_nodenum
    
    # 隣接リストの更新
    graph[pc_nodenum].append((qc_nodenum, 0))
    graph[qc_nodenum].append((pc_nodenum, 0))
    
    graph[pc_nodenum].append((pz_nodenum, 0))
    graph[qc_nodenum].append((qz_nodenum, 0))
    
    graph[pz_nodenum].append((pc_nodenum, 1))
    graph[qz_nodenum].append((qc_nodenum, 1))
    
num2node = {ni: (stati, compi) for (stati, compi), ni in node2num.items()}

INF = 1<<62
ans = INF

if start == -1:
    print(-1)

else:
    dist = dijkstra(graph, start, INF)
    for nodei in range(len(keyset)):
        if num2node[nodei][0] == n:
            ans = min(ans, dist[nodei])
            
    print(ans)

Submission status: Wrong Answer

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 defaultdict
from heapq import heappush, heappop

# 入力
n,m = li()

# (station, company) をキーとする隣接リスト adjdic
adjdic = defaultdict(set)


for _ in range(m):
    p, q, c = li()
    
    adjdic[(p,c)].add((0, q, c))
    adjdic[(q,c)].add((0, p, c))
    
    if p != 1:
        adjdic[(p,c)].add((0, p, 0))
    
    if q != 1:
        adjdic[(q,c)].add((0, q, 0))
    
    adjdic[(p,0)].add((1, p, c))
    adjdic[(q,0)].add((1, q, c))



# ダイクストラ
que = [(0, 1, 0)]

visited = defaultdict(int)
ans = float('inf')
while que:
    cost, cur, comp = heappop(que)
    if cur == n:
        ans = cost
        break
    
    for fee, nexnode, nexcomp in adjdic[(cur, comp)]:
        if visited[(nexnode, nexcomp)] == 0:
            visited[(nexnode, nexcomp)] = 1
            heappush(que, (cost+fee, nexnode, nexcomp))
            
        
print(-1 if ans == float('inf') else ans)

Submission status: Wrong Answer

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 defaultdict
from heapq import heappush, heappop

# 入力
n,m = li()

# (station, company) をキーとする隣接リスト adjdic
adjdic = defaultdict(set)


for _ in range(m):
    p, q, c = li()
    
    adjdic[(p,c)].add((0, q, c))
    adjdic[(q,c)].add((0, p, c))
    
    adjdic[(p,c)].add((0, p, 0))
    adjdic[(q,c)].add((0, q, 0))
    
    adjdic[(p,0)].add((1, p, c))
    adjdic[(q,0)].add((1, q, c))



# ダイクストラ
que = [(0, 1, 0)]

visited = defaultdict(int)
ans = float('inf')
while que:
    cost, cur, comp = heappop(que)
    if cur == n:
        ans = cost
        break
    
    for fee, nexnode, nexcomp in adjdic[(cur, comp)]:
        if visited[(nexnode, nexcomp)] == 0:
            visited[(nexnode, nexcomp)] = 1
            heappush(que, (cost+fee, nexnode, nexcomp))
            
        
print(-1 if ans == float('inf') else ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
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

n,m = li()
comp = [set() for _ in range(10**6)]
sta = [set() for _ in range(n)]
for _ in range(m):
    p,q,c = li_()
    comp[c].add(p)
    comp[c].add(q)
    sta[p].add(c)
    sta[q].add(c)

que = deque([])
que.append((0,0))

INF = pow(10,10)
dist = [INF]*n
dist[0] = 0

while que:
    cost, cur = que.popleft()
    for company in sta[cur]:
        for station in comp[company]:
            if dist[station] == INF:
                dist[station] = cost + 1
                que.append((cost+1, station))
    
print(-1) if dist[n-1] == INF else print(dist[n-1])

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
mod =10**7
table=defaultdict(set)
visit=defaultdict(int)
for i in range(M):
    a,b,c=map(int,input().split())
    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

H=deque()
H.append((1,0))
visit[1]=1
ans=mod
while H:
    #print(H)
    x,cost=H.popleft()
    if x==N:
        ans=min(ans,cost)
        break
    for y in table[x]:
        if visit[y]==1:
            continue
        visit[y]=1
        if x<=10**5 and mod<=y:
            H.append((y,cost+1))
        else:
            H.appendleft((y,cost))
if ans==mod:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
mod =10**6
table=defaultdict(set)
visit=defaultdict(int)
for i in range(M):
    a,b,c=map(int,input().split())
    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
#print(table)

H=deque()
H.append((1,0))
visit[1]=1
ans=mod
while H:
    #print(H)
    x,cost=H.popleft()
    if x==N:
        ans=cost
        break
    for y in table[x]:
        if visit[y]==1:
            continue
        visit[y]=1
        if x<=mod and mod<=y:
            H.append((y,cost+1))
        else:
            H.appendleft((y,cost))
if ans==mod:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
N,M=map(int,input().split())
mod =10**6
table=defaultdict(set)
visit=defaultdict(int)
for i in range(M):
    a,b,c=map(int,input().split())
    table[a].add((a+c*mod,1))
    table[b].add((b+c*mod,1))
    table[a+c*mod].add((a,0))
    table[b+c*mod].add((b,0))
    table[a+c*mod].add((b+c*mod,0))
    table[b+c*mod].add((a+c*mod,0))
    visit[a]=0
    visit[b]=0
    visit[b+c*mod]=0
    visit[a+c*mod]=0
#print(table)

H=deque()
H.append((1,0))
visit[1]=1
ans=mod
while H:
    #print(H)
    x,cost=H.popleft()
    if x==N:
        ans=cost
        break
    for y,c in table[x]:
        if visit[y]==1:
            continue
        visit[y]=1
        if c==1:
            H.append((y,cost+1))
        else:
            H.appendleft((y,cost))
if ans==mod:
    print(-1)
else:
    print(ans)