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: Runtime Error

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(2*(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: Runtime Error

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

print(BFS(1))

Submission status: Runtime Error

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

print(BFS(1))

Submission status: Runtime Error

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

print(BFS(1))

Submission status: Runtime Error

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

print(BFS(0))

Submission status: Runtime Error

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

print(BFS(0))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq

N, M = map(int, input().split())
D = {}
Edges = []
Edge_dict = {}


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(M)
for i in range(M):
    p, q, c = map(int, input().split())
    p, q = p-1, q-1
    Edges.append((p, q, c))

    if (p, c) in D:
        UF.union(D[p, c], i)
    D[p, c] = i
    Edge_dict.setdefault(p, set()).add(c)

    if (q, c) in D:
        UF.union(D[q, c], i)
    D[q, c] = i
    Edge_dict.setdefault(q, set()).add(c)

UF.all_find()

Firm_Node = {}
for i in range(M):
    p, q, c = Edges[i]
    Firm_Node.setdefault(UF.par[i], set()).add(p)
    Firm_Node.setdefault(UF.par[i], set()).add(q)

G = {}
for firm, node in Firm_Node.items():
    for n in node:
        G.setdefault(n, []).append(firm + N)
        G.setdefault(firm + N, []).append(n)


def dijkstra(x):
    d = defaultdict(float)
    for key in G.keys():
        d[key] = float('inf')

    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node in G[u]:
            if (node not in visited) and d[node] > d[u] + 1:
                d[node] = d[u] + 1
                heapq.heappush(hq, (d[u]+1, node))
    return d


dist = dijkstra(0)
print(dist[N-1] // 2 if dist[N-1] not in [0, float('inf')] else -1)

Submission status: Runtime Error

Solution code:
from collections import deque

N, M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
F_C_of_S = [{} for i in range(N)]
# Companies of Station
C_of_S = {}

# def Union-find
parent = {i:i for i in range(M)}
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y);
    if px < py:
        parent[py] = px
    else:
        parent[px] = py


# Union-find
pqcs = []
#stations of company
S_of_C = {}
for i in range(M):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1;
    pqcs += [(p, q, c)]

    if not 10**6+c in parent:
        parent[10**6+c] = i
    else:
        unite(10**6+c, i)

    C_of_S.setdefault(p, set()).add(root(i))
    C_of_S.setdefault(q, set()).add(root(i))
    c_set = S_of_C.setdefault(root(i), set())
    c_set.add(p)
    c_set.add(q)


Q = deque([(0, 0, 0)])
# cost to go to the station from station_0
dist = [float('inf')] * N
dist[0] = 0
# cost to get on the line
line_dist = [float('inf')] * M

while Q:
    cost, v, flag = Q.popleft()
    if not (flag):  # (flag == 0) then line_dist_update
        # v is station
        for l in C_of_S[v]:
            if (cost < line_dist[l]):
                line_dist[l] = cost
                Q.appendleft((cost, l, 1))
    else:  # (flag == 1) then dist_update
        # v is company
        for s in S_of_C[v]:
            if (cost + 1 < dist[s]):
                dist[s] = cost + 1
                Q.append((cost + 1, s, 0))

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

Submission status: Runtime Error

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

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

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


#Union-find
pqcs = []
#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]:
		#Numbering in order of appearance
		F_C_of_S[p][c] = i
	#else
	else:
		unite(F_C_of_S[p][c], i)
	#set a line that can ride from the station
	C_of_S.setdefault(p, set()).add(c)
	
	if not (c in F_C_of_S[q]):
		F_C_of_S[q][c] = i
	else:
		unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)
	
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)

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


Q = deque([(0, 0, 0)])
#cost to go to the station from station_0
dist = [float('inf')]*N
dist[0] = 0
#cost to get on the line 
gdist = [float('inf')]*M

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

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

Submission status: Runtime Error

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

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

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


#Union-find
pqcs = []
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]:
		#Numbering in order of appearance
		F_C_of_S[p][c] = i
	#else
	else:
		unite(F_C_of_S[p][c], i)
	#set a line that can ride from the station
	C_of_S.setdefault(p, set()).add(c)
	
	if not (c in F_C_of_S[q]):
		F_C_of_S[q][c] = i
	else:
		unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)
	
	#stations of company
	S_of_C = {}
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)
	
"""
#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = pqcs[i]
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)
"""

Q = deque([(0, 0, 0)])
#cost to go to the station from station_0
dist = [float('inf')]*N
dist[0] = 0
#cost to get on the line 
gdist = [float('inf')]*M

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

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

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
cs = set{}
for i in range(M):
	p,q,c = map(int, input().split())
	cs += c
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
c_num = len(cs)
distance = [[float('inf')]*(c_num+1) for _ in range(N)]
distance[0][0] = 0
min_distance = [float('inf')]*N
min_distance[0] = 0
Q = [[0, 0]]

while Q:
	s_now,c_now = heappop(Q)
	for t, c in edges[s_now]:
		if min_distance[t] > distance[s_now][c_now] + (c_now != c):
			distance[t][c] = distance[s_now][c_now] + (c_now != c)
			min_distance[t] = distance[t][c]
			heappush(Q, [t, c])
print(min_distance[N-1] if min_distance[N-1] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
c_max = 0
for i in range(M):
	p,q,c = map(int, input().split())
	c_max = max(c, c_max)
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
distance = [[float('inf')]*(c_max+1) for _ in range(N)]
distance[0][0] = 0
min_distance = [float('inf')]*N
min_distance[0] = 0
Q = deque([[0,0]])


flag = False
while Q:
	s_now,c_now = Q.popleft()
	for t, c in edges[s_now]:
		if min_distance[t] > distance[s_now][c_now] + (c_now != c):
			distance[t][c] = distance[s_now][c_now] + (c_now != c)
			min_distance[t] = distance[t][c]
			if c_now == c:
				Q.appendleft([t, c])
				continue
			Q.append([t, c])
print(min_distance[N-1] if min_distance[N-1] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
c_max = 0
for i in range(M):
	p,q,c = map(int, input().split())
	c_max = max(c, c_max)
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
distance = [[float('inf')]*(c_max+1) for _ in range(N)]
distance[0][0] = 0
Q = deque([[0,0]])


flag = False
while Q:
	s_now,c_now = Q.popleft()
	for t, c in edges[s_now]:
		t_dist = min(distance[t])
		if t_dist > distance[s_now][c_now] + (c_now != c):
			distance[t][c] = distance[s_now][c_now] + (c_now != c)
			if c_now == c:
				Q.appendleft([t, c])
				continue
			Q.append([t, c])
d = min(distance[N-1])
print(d if d != float('inf') else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
c_max = 0
for i in range(M):
	p,q,c = map(int, input().split())
	c_max = max(c, c_max)
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
distance = [[float('inf')]*(c+1) for _ in range(N)]
distance[0][0] = 0
Q = deque([[0,0]])


flag = False
while Q:
	s_now,c_now = Q.popleft()
	for t, c in edges[s_now]:
		t_dist = min(distance[t])
		if t_dist > distance[s_now][c_now] + (c_now != c):
			distance[t][c] = distance[s_now][c_now] + (c_now != c)
			if c_now == c:
				Q.appendleft([t, c])
				continue
			Q.append([t, c])
d = min(distance[N-1])
print(d if d != float('inf') else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M = map(int, input().split())
if M == 0:
	print(-1)
	exit()
Q = {0:deque([1])}
distance = {1:0}

#辺へ重み付け
edges = {}
for _ in range(M):
	p,q,c = map(int, input().split())
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

flag = False
while 1:
	for i in range(len(Q)):                            
		if not (Q[i]):
			continue
		flag = True
		target_min_ind = Q[i].popleft()
		target_node = edges[target_min_ind]
		break
	if not (flag):
		break

	for key, value in target_node.items():
		distance.setdefault(key, float('inf'))
		dist = distance[target_min_ind] + value
		if distance[key] > dist:
			distance[key] = dist
			Q.setdefault(dist, deque())
			Q[dist].append(key)
		if key == N:
			flag = False
	if not (flag):
		break

print(distance[N] if distance[N] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
Q = {0:deque([1])}
distance = {1:0}

#辺へ重み付け
edges = {}
for p,q,c in (list(map(int, input().split())) for _ in range(M)):
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

flag = False
while 1:
	for i in range(len(Q)):                            
		if not (Q[i]):
			continue
		flag = True
		target_min_ind = Q[i].popleft()
		target_node = edges[target_min_ind]
		break
	if not (flag):
		break

	for key, value in target_node.items():
		distance.setdefault(key, float('inf'))
		dist = distance[target_min_ind] + value
		if distance[key] > dist:
			distance[key] = dist
			Q.setdefault(dist, deque())
			Q[dist].append(key)
		if key == N:
			flag = False
	if not (flag):
		break

print(distance[N] if distance[N] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    if temp_min_dist == float('inf'):
        break
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    flag = False
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1] if distance[N-1] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    flag = False
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1] if distance[N-1] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
"""
if M == 0:
    print(-1)
    exit()
"""
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    flag = False
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1] if distance[N-1] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
"""
if M == 0:
    print(-1)
    exit()
"""
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    flag = False
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1] if distnce[N-1] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1])