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: Time Limit Exceeded

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

def solve(n, m, g):

    dist = {}
    que = []
    for tpl in g[0]:
        w, c = tpl
        dist[(0, c)] = 0
        heapq.heappush(que, (0, (0, c)))

    while len(que):
        d, vc = heapq.heappop(que)
        v, cv = vc
        for wc in g[v]:
            w, cw = wc
            if cw == cv:
                alt = d
            else:
                alt = d + 1
            if not wc in dist or alt < dist[wc]:
                dist[wc] = alt
                heapq.heappush(que, (alt, wc))

    min_d = 10 ** 6
    for wc in g[n - 1]:
        if wc in dist:
            min_d = min(min_d, dist[wc])

    if min_d == 10 ** 6:
        return -1
    else:
        return min_d + 1


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

    print(solve(n, m, g))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 :float("inf"))
		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 = [float('inf') 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])
	edges[p-1 + t * n].append([p-1 + 0 * n, 0])
	edges[q-1 + t * n].append([q-1 + 0 * n, 0])
	edges[p-1 + 0 * n].append([p-1 + t * n, 1])
	edges[q-1 + 0 * n].append([q-1 + t * n, 1])

#print(edges.items())
d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res == float("inf"):
	print(-1)
else:
	print(res)

Submission status: Time Limit Exceeded

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] = 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: Time Limit Exceeded

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] = 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: Time Limit Exceeded

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*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
    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: Time Limit Exceeded

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((q, c))
    Edge[q].append((p, c))
    comp.add(c)
dist = {(1, 0): 0}
Q = deque()
Q.append((1, 0))
visited = set()
while Q:
    vn, cp = Q.pop()
    if (vn, cp) in visited:
        continue
    visited.add((vn, cp))
    for vf, cf in Edge[vn]:
        if (vf, cp) in visited:
            continue
        if cp == cf:
            dist[(vf, cf)] = min(dist.get((vf, cf), 10**9), dist.get((vn, cp), 10**9))
            Q.append((vf, cf))
        else:
            dist[(vf, cf)] = min(dist.get((vf, cf), 10**9), 1 + dist.get((vn, cp), 10**9))
            Q.appendleft((vf, cf))
L = [dist.get((N, c), 10**9) for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

Submission status: Time Limit Exceeded

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

# 入力・隣接リスト作成
n,m = li()
graph = defaultdict(set)
geta = pow(10,7)

for _ in range(m):
    p,q,c = li()
    
    graph[p + c*geta].add(q + c*geta)
    graph[q + c*geta].add(p + c*geta)
    
    graph[p + c*geta].add(p)
    graph[q + c*geta].add(q)
    
    graph[p].add(p + c*geta)
    graph[q].add(q + c*geta)
    
que = deque()
que.append((0, 1))
visited = set()

ans = -1

while que:
    (cost, node) = que.popleft()
    
    if node in visited:
        continue
    
    elif node % geta == n:
        ans = cost
        break
    
    visited.add(node)
    
    
    for nex in graph[node]:
        if nex in visited:
            continue
        
        elif node <= n and nex > n:
            que.append((cost+1, nex))
            
        else:
            que.appendleft((cost, nex))
    
print(ans)

Submission status: Time Limit Exceeded

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
from collections import defaultdict

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

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 = defaultdict(set)
node2num = {}
num2node = {}
keyset = set()

for _ in range(m):
    p,q,c = li()

    # ノードの登録
    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)
    

    # 隣接リストの更新
    graph[pc_nodenum].add((qc_nodenum, 0))
    graph[qc_nodenum].add((pc_nodenum, 0))
    
    graph[pc_nodenum].add((pz_nodenum, 0))
    graph[qc_nodenum].add((qz_nodenum, 0))
    
    graph[pz_nodenum].add((pc_nodenum, 1))
    graph[qz_nodenum].add((qc_nodenum, 1))
    
INF = 1<<62
start = get_nodenum(1, 0, keyset, node2num)
if m == 0:
    print(-1)
    
else:
    num2node = {ni: (stati, compi) for (stati, compi), ni in node2num.items()}
    del node2num
    
    ans = dijkstra(graph, start, INF, num2node, n)
    
    print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

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()
    visit[x] = 1
    if x==N:
        ans=min(ans,cost)
        break
    for y in table[x]:
        if visit[y]==1:
            continue
        if x<=10**5 and mod<=y:
            H.append((y,cost+1))
        else:
            H.appendleft((y,cost))
if ans==mod:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
N, M = map(int, input().split())
Rails = [[] for _ in range(N)]

def constant_factory(value): return lambda: value
Costs = defaultdict(constant_factory(1000000000))
Visited = defaultdict(constant_factory(False))

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

Q = [(0, 0, -1)]
heapq.heapify(Q)
while Q:
    currentCost, currentNode, currentCompany = heapq.heappop(Q)
    if not Visited[(currentNode, currentCompany)]:
        Visited[(currentNode, currentCompany)] = True
        if currentCompany == -1:
            for nextNode, nextCompany in Rails[currentNode]:
                if not Visited[(nextNode, nextCompany)]:
                    if Costs[(nextNode, nextCompany)] > currentCost + 1:
                        Costs[(nextNode, nextCompany)] = currentCost + 1
                        heapq.heappush(Q, (currentCost + 1, nextNode, nextCompany))
        else:
            if not Visited[(currentNode, -1)]:
                if Costs[(currentNode, -1)] > currentCost:
                    Costs[(currentNode, -1)] = currentCost
                    heapq.heappush(Q, (currentCost, currentNode, -1))
            for nextNode, nextCompany in Rails[currentNode]:
                if nextCompany == currentCompany and not Visited[(nextNode, nextCompany)]:
                    if Costs[(nextNode, nextCompany)] > currentCost:
                        Costs[(nextNode, nextCompany)] = currentCost
                        heapq.heappush(Q, (currentCost, nextNode, nextCompany))
minCost = Costs[(N-1, -1)]
print(minCost if minCost < 1000000000 else -1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
Rails = [[] for _ in range(N)]
Costs = {(i, -1): 1000000000 for i in range(N)}
Visited = {(i, -1): False for i in range(N)}
for _ in range(M):
    p, q, c = map(int, input().split())
    Rails[p-1].append((q-1, c))
    Rails[q-1].append((p-1, c))
    Costs[(p-1, c)] = 1000000000
    Costs[(q-1, c)] = 1000000000
    Visited[(p-1, c)] = False
    Visited[(q-1, c)] = False

Q = [(0, 0, -1)]
heapq.heapify(Q)
while Q:
    currentCost, currentNode, currentCompany = heapq.heappop(Q)
    if not Visited[(currentNode, currentCompany)]:
        Visited[(currentNode, currentCompany)] = True
        if currentCompany == -1:
            for nextNode, nextCompany in Rails[currentNode]:
                if not Visited[(nextNode, nextCompany)]:
                    if Costs[(nextNode, nextCompany)] > currentCost + 1:
                        Costs[(nextNode, nextCompany)] = currentCost + 1
                        heapq.heappush(Q, (currentCost + 1, nextNode, nextCompany))
        else:
            if not Visited[(currentNode, -1)]:
                if Costs[(currentNode, -1)] > currentCost:
                    Costs[(currentNode, -1)] = currentCost
                    heapq.heappush(Q, (currentCost, currentNode, -1))
            for nextNode, nextCompany in Rails[currentNode]:
                if nextCompany == currentCompany and not Visited[(nextNode, nextCompany)]:
                    if Costs[(nextNode, nextCompany)] > currentCost:
                        Costs[(nextNode, nextCompany)] = currentCost
                        heapq.heappush(Q, (currentCost, nextNode, nextCompany))
minCost = Costs[(N-1, -1)]
print(minCost if minCost < 1000000000 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G[(a-1,c-1)].add((b-1,c-1,0))
  G[(b-1,c-1)].add((a-1,c-1,0))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G[(i,-1)].add((i,c,1))
    G[(i,c)].add((i,-1,0))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  ans=0
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G[(a,c)]:
      if not visited[(i[0],i[1])]:
        if i[2]==0:
          stack.appendleft((i[0],i[1],m))
        else:
          stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print(BFS(0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
    G0[(i,c)].add((i,-1))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G0[(a,c)]:
      if not visited[(a,c)]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[(a,c)]:
        stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print(BFS(0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G0[(a,c)]:
      if not visited[i[0]]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[i[0]]:
        stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print(BFS(0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    visited[(a,c)]=True
    for i in G0[(a,c)]:
      if not visited[i]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[i]:
        stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（ダイクストラ法）
def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = defaultdict(lambda: INF)
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))

    while PQ:
        c, vNow = heappop(PQ)
        if c > costs[vNow]: continue

        numUsed += 1
        if numUsed == numV: break

        costNow = c
        for v2, wt in adjList[vNow]:
            c2 = costNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))

    return costs


N, M = map(int, input().split())
adjL = defaultdict(list)
for _ in range(M):
    p, q, c = map(int, input().split())
    adjL[(p, c)].append(((q, c), 0))
    adjL[(q, c)].append(((p, c), 0))
    adjL[(p, 0)].append(((p, c), 1))
    adjL[(p, c)].append(((p, 0), 1))
    adjL[(q, 0)].append(((q, c), 1))
    adjL[(q, c)].append(((q, 0), 1))

costs = Dijkstra(adjL, (1, 0))
if costs[(N, 0)] == INF:
    print(-1)
else:
    print(costs[(N, 0)] // 2)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10000)


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


def bfs01(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    d = {}
    prev = {}
    q = []
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = sys.maxsize

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

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


@mt
def slv(N, M, PQC):

    g = defaultdict(dict)
    for p, q, c in PQC:
        g[(c, p)][(c, q)] = 0
        g[(c, q)][(c, p)] = 0
        g[(c, p)][(p, )] = 0
        g[(c, q)][(q, )] = 0
        g[(p, )][(c, p)] = 1
        g[(q, )][(c, q)] = 1

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


def main():
    N, M = read_int_n()
    PQC = [read_int_n() for _ in range(M)]
    print(slv(N, M, PQC))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10000)


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


def Dijkstra(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    d = {}
    prev = {}
    q = []
    for v in V:
        if v == s:
            d[v] = 0
        else:
            d[v] = sys.maxsize

    if s not in d:
        return d
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d


@mt
def slv(N, M, PQC):

    g = defaultdict(dict)
    for p, q, c in PQC:
        g[(c, p)][(c, q)] = 0
        g[(c, q)][(c, p)] = 0
        g[(c, p)][(p, )] = 0
        g[(c, q)][(q, )] = 0
        g[(p, )][(c, p)] = 1
        g[(q, )][(c, q)] = 1

    d = Dijkstra(g, (1,))
    return -1 if (N, ) not in d else d[(N, )]


def main():
    N, M = read_int_n()
    PQC = [read_int_n() for _ in range(M)]
    print(slv(N, M, PQC))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

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


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 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))

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

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

UF.all_find()

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

G = defaultdict(list)
for firm, node in Firm_Node.items():
    for n in node:
        G[n].append(firm + N)
        G[firm + N].append(n)


def dijkstra(x):
    d = {x: 0, N-1: 10**9}
    visited = {x}

    # d, u
    queue = deque([(0, x)])

    while queue:
        u = queue.pop()[1]
        visited.add(u)

        for node in G[u]:
            d.setdefault(node, float('inf'))
            if (node not in visited) and d[node] > d[u] + 1:
                d[node] = d[u] + 1
                if d[N-1] < 10**9:
                    return d
                queue.appendleft([d[u]+1, node])
    return d


dist = dijkstra(0)
print(dist[N-1] // 2 if dist[N-1] < 2*M else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

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


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

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

UF.all_find()

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

G = defaultdict(list)
for firm, node in Firm_Node.items():
    for n in node:
        G[n].append(firm + N)
        G[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
    queue = deque([(0, x)])

    while queue:
        u = queue.pop()[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
                queue.appendleft([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)