Problem:


Score : 600 points

Problem Statement

Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.

The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.

You can change trains at a station where multiple lines are available.

The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.

Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq 2×10^5

1 \leq p_i \leq N (1 \leq i \leq M)

1 \leq q_i \leq N (1 \leq i \leq M)

1 \leq c_i \leq 10^6 (1 \leq i \leq M)

p_i \neq q_i (1 \leq i \leq M)

Input

The input is given from Standard Input in the following format:

N M
p_1 q_1 c_1
:
p_M q_M c_M

Output

Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.

Sample Input 1

3 3
1 2 1
2 3 1
3 1 2

Sample Output 1

1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

Sample Input 2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

Sample Output 2

2

First, use company 1's lines: 1 → 3 → 2 → 5 → 6. Then, use company 5's lines: 6 → 7 → 8. The fare is 2 yen.

Sample Input 3

2 0

Sample Output 3

-1



Sample input:
3 3
1 2 1
2 3 1
3 1 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
from collections import deque
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 = []
#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: Wrong Answer

Solution code:
from heapq import heappop, heappush
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
cs = []
c_num = 1
for i in range(M):
	p,q,c = map(int, input().split())
	if not c in cs:
		cs += [c]
		c = c_num
		c_num += 1
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
cs.clear()
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: Wrong Answer

Solution code:
from heapq import heappop, heappush
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 = [[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: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

flag = False
while Q: 
	dist,now,line = heappop(Q)
	for t, c in edges[now]:
		if distance[t] > distance[now] + (line != c):
			distance[t] = distance[now] + (line != c)
			heappush(Q, [distance[t], t, c])
			if t == N-1:
				flag = True
	if (flag):
		break
print(distance[N-1] if distance[N-1] != float('inf') else -1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [[float("inf"),0] for i in range(num)]
    dist[start] = [0,0]
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for i,j in lis[u]:
            if dist[i][0] > du[0] + (0 if j == du[1] else 1):
                dist[i] = [du[0] + (0 if j == du[1] else 1), j]
                heappush(q, [dist[i], i])
    return dist
n,m = map(int, input().split())
lis = [[] for i in range(n)]
for i in range(m):
    q,p,c = map(int, input().split())
    lis[q-1].append([p-1,c])
    lis[p-1].append([q-1,c])
ans = dijkstra(n,0)
print(ans[n-1][0] if ans[n-1][0] != float("inf") else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
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
Q = [deque([1]), deque([])]
distance = {1:0}

#辺へ重み付け
edges = {}
for p,q,c in pqcs:
	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)

while (Q[0] or Q[1]):
	target_min_ind = Q[0].popleft() if (Q[0]) else Q[1].popleft()
	target_node = edges[target_min_ind]

	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[0].append(key) if dist == 0 else Q[1].append(key)
		if key == N:
			print(distance[N] if distance[N] != float('inf') else -1)
			exit()

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int,input().split())
if M == 0:
    print(-1)
    exit()

es = [[] for i in range(N)]
for i in range(M):
    p,q,c = map(lambda x:int(x)-1, input().split())
    es[p].append((q,c))
    es[q].append((p,c))

INF = N*999
costs = [INF] * N
costs[0] = 0
q = deque([(0,-1)])
while q:
    v,c1 = q.popleft()
    if v == N-1:
        break
    for to,c2 in es[v]:
        trans = int(c1 != c2)
        newcost = costs[v] + trans
        if newcost >= costs[to]: continue
        costs[to] = newcost
        if trans:
            q.append((to,c2))
        else:
            q.appendleft((to,c2))
print(costs[N-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ES = []
D = [{} for i in range(N)]

*parent, = 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

E = {}
for i in range(M):
    p, q, c = map(int, input().split()); p -= 1; q -= 1
    ES.append((p, q, c))
    if c in D[p]:
        unite(D[p][c], i)
    E.setdefault(p, set()).add(c)
    if c in D[q]:
        unite(D[q][c], i)
    D[p][c] = root(i)
    D[q][c] = root(i)
    E.setdefault(q, set()).add(c)
P = {}
for i in range(M):
    p, q, c = ES[i]
    s = P.setdefault(root(i), set())
    s.add(p); s.add(q)

from collections import deque
que = deque([(0, 0, 0)])
INF = 10**18
dist = [INF]*N
dist[0] = 0
gdist = [INF]*M

while que:
    cost, v, t = que.popleft()
    if t:
        # edge
        if gdist[v] < cost or v not in P:
            continue
        for w in P[v]:
            if cost + 1 < dist[w]:
                dist[w] = cost + 1
                que.append((cost + 1, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for w in D[v].values():
            if cost < gdist[w]:
                gdist[w] = cost
                que.appendleft((cost, w, 1))

print(dist[N-1] if dist[N-1] < INF else -1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ES = []
D = {}

*parent, = 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

E = {}
for i in range(M):
    p, q, c = map(int, input().split()); p -= 1; q -= 1
    ES.append((p, q, c))
    if (p, c) in D:
        unite(D[p, c], i)
    D[p, c] = root(i)
    E.setdefault(p, set()).add(c)
    if (q, c) in D:
        unite(D[q, c], i)
    D[q, c] = root(i)
    E.setdefault(q, set()).add(c)
#P = [[] for i in range(M)]
P = {}
for i in range(M):
    j = root(i)
    p, q, c = ES[i]
    s = P.setdefault(j, set())
    s.add(p)
    s.add(q)

from collections import deque
que = deque([(0, 0, 0)])
INF = 10**18
dist = [INF]*N
dist[0] = 0
gdist = [INF]*M

while que:
    cost, v, t = que.popleft()
    if t:
        # edge
        if gdist[v] < cost or v not in P:
            continue
        for w in P[v]:
            if cost + 1 < dist[w]:
                dist[w] = cost + 1
                que.append((cost + 1, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for c in E[v]:
            w = D[v, c]
            if cost < gdist[w]:
                gdist[w] = cost
                que.appendleft((cost, w, 1))

print(dist[N-1] if dist[N-1] < INF else -1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    p, q, c = map(int, input().split())
    G[p-1].append((q-1, c))
    G[q-1].append((p-1, c))

from collections import deque
que = deque([(0, 0, -1)])
dist = [10**18]*N
dist[0] = 0

while que:
    cost, v, c = que.popleft()
    if dist[v] < cost:
        continue
    for w, d in G[v]:
        if c == d:
            if cost < dist[w]:
                dist[w] = cost
                que.appendleft((cost, w, c))
        else:
            if cost + 1 < dist[w]:
                dist[w] = cost + 1
                que.append((cost + 1, w, d))

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**8)

def dfs(s,c,gp,g,edge_visited):
    gp.append(s)
    for nx,co,i in g[s]:
        if not edge_visited[i] and c==co:
            edge_visited[i]=True
            dfs(nx,c,gp,g,edge_visited)
    return gp

def main():
    n,m=map(int,raw_input().split())
    g=[[] for _ in xrange(n)]
    gc=[[] for _ in xrange(10**6)]

    for i in xrange(m):
        p,q,c=map(int,raw_input().split())
        p-=1;q-=1;c-=1
        g[p].append([q,c,i])
        g[q].append([p,c,i])

    edge_visited=[False]*m
    for i in xrange(n):
        for q,c,ne in g[i]:
            if not edge_visited[ne]:
                edge_visited[ne]=True
                tmp=[i]
                gp=dfs(q,c,tmp,g,edge_visited)
                gc[c].append(gp)
    visited=[False]*n
    q=deque([[0,1]])
    visited[0]=True
    while len(q)!=0:
        p,dist=q.popleft()
        for nx,c,i in g[p]:
            for nxg in gc[c]:
                for j in nxg:
                    if not visited[j]:
                        visited[j]=True
                        if j==n-1:
                            print(dist)
                            exit()
                        q.append([j,dist+1])
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n,m=map(int,raw_input().split())
    g=[[] for _ in xrange(n)]
    gc=[[] for _ in xrange(10**6)]

    for i in xrange(m):
        p,q,c=map(int,raw_input().split())
        p-=1;q-=1;c-=1
        g[p].append(c)
        g[q].append(c)
        gc[c].append(p)
        gc[c].append(q)

    visited=[False]*n
    q=deque([[0,1]])
    visited[0]=True
    while len(q)!=0:
        p,dist=q.popleft()
        for i in g[p]:
            for j in gc[i]:
                if not visited[j]:
                    visited[j]=True
                    if j==n-1:
                        print(dist)
                        exit()
                    q.append([j,dist+1])
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n,m=map(int,raw_input().split())
    g=[[] for _ in xrange(n)]
    gc=[[] for _ in xrange(10**6)]
    mxc=0

    for i in xrange(m):
        p,q,c=map(int,raw_input().split())
        p-=1;q-=1;c-=1
        g[p].append(c)
        g[q].append(c)
        gc[c].append(p)
        gc[c].append(q)
        mxc=max(mxc,c+1)

    visited=[False]*mxc
    q=deque([[0,1]])
    while len(q)!=0:
        p,dist=q.popleft()
        for i in g[p]:
            if not visited[i]:
                visited[i]=True
                for j in gc[i]:
                    if j!=p:
                        if j==n-1:
                            print(dist)
                            exit()
                        q.append([j,dist+1])
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n,m=map(int,raw_input().split())
    g=[[] for _ in xrange(n)]
    gc=[[] for _ in xrange(10**6)]
    mxc=0

    for i in xrange(m):
        p,q,c=map(int,raw_input().split())
        p-=1;q-=1;c-=1
        g[p].append(c)
        g[q].append(c)
        gc[c].append(p)
        gc[c].append(q)
        mxc=max(mxc,c+1)

    visited=[False]*mxc
    q=deque([[0,1]])
    while len(q)!=0:
        p,dist=q.popleft()
        for i in g[p]:
            if not visited[i]:
                visited[i]=True
                for j in gc[i]:
                    if j!=p:
                        if j==n-1:
                            print(dist)
                            exit()
                        q.append([j,dist+1])
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n,m=map(int,raw_input().split())
    g=[[] for _ in xrange(n)]
    gc=[[] for _ in xrange(10**6)]
    mxc=0

    for i in xrange(m):
        p,q,c=map(int,raw_input().split())
        p-=1;q-=1;c-=1
        g[p].append(c)
        g[q].append(c)
        gc[c].append(p)
        gc[c].append(q)
        mxc=max(mxc,c+1)

    visited=[False]*mxc
    q=deque([[0,1]])
    while len(q)!=0:
        p,dist=q.popleft()
        for i in g[p]:
            if not visited[i]:
                for j in gc[i]:
                    if j!=p:
                        if j==n-1:
                            print(dist)
                            exit()
                        q.append([j,dist+1])
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
for i in xrange(m):
    p,q,c=map(int,raw_input().split())
    p-=1;q-=1
    g[p].append([q,c,i,0])
    g[q].append([p,c,i,1])
if g[0]==[]:
    print(-1)
    exit()

cost=[float('inf')]*n
cost[0]=0
evisited=[[0]*2 for _ in xrange(m)]
q=deque([(0,0)])
while len(q)!=0:
    p,e=q.popleft()
    for i,j,k,l in g[p]:
        if evisited[k][l]==0:
                evisited[k][l]=1
                q.append([i,j])
                if p==0:
                    cost[i]=1
                else:
                    for a,b,c,d in g[p]:
                        if e==b:
                            cost[a]=min(cost[a],cost[p])
                        else:
                            cost[a]=min(cost[a],cost[p]+1)
print cost[n-1]

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  read = sys.stdin.read
  
  N,M=map(int,input().split())

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

  INF = 10**6
  m = map(lambda x:int(x)-1, read().split())
  *pqc, = zip(m, m, m)
  del m

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for v in range(N):
    if len(to1d[v])<=1: continue
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  read = sys.stdin.read
  
  N,M=map(int,input().split())

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

  INF = 10**6
  m = map(lambda x:int(x)-1, read().split())
  *pqc, = zip(m, m, m)

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for v in range(N):
    if len(to1d[v])<=1: continue
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,M=map(int,input().split())

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

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for v in range(N):
    if len(to1d[v])<=1: continue
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())

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

INF = 10**6
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

to1d={v:{} for v in range(N)}
count=2
for p,q,c in pqc:
  if not to1d[p].get(c):
    to1d[p][c] = count
    count += 1
  if not to1d[q].get(c):
    to1d[q][c] = count
    count += 1

G = [{} for _ in range(count)]
for p,q,c in pqc:
  v1,v2 = to1d[p][c],to1d[q][c]
  G[v1][v2] = G[v2][v1] = 0
  
for v in range(N):
  if len(to1d[v])<=1: continue
  tmp = list(to1d[v].keys())
  for i in range(len(tmp)-1):
    for j in range(i+1,len(tmp)):
      v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
      G[v1][v2] = G[v2][v1] = 1
        
def dijkstra(start = 0, goal = 1):
    from heapq import heappop, heappush
    NN = len(G)
    d = [INF]*NN
    d[start] = 0
    que = []
    heappush(que, start)
    while que:
        p = divmod(heappop(que),NN)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, d[u]*NN+u)
        if v == goal: return d[goal]
    return d[goal]

for c in to1d[0].keys():
  v = to1d[0][c]
  G[0][v] = 1
for c in to1d[N-1].keys():
  v = to1d[N-1][c]
  G[v][1] = 0
  
ans = dijkstra(0,1)
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 

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

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

INF = 10**6
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

to1d={v:{} for v in range(N)}
count=2
for p,q,c in pqc:
  if not to1d[p].get(c):
    to1d[p][c] = count
    count += 1
  if not to1d[q].get(c):
    to1d[q][c] = count
    count += 1

G = [{} for _ in range(count)]
for p,q,c in pqc:
  v1,v2 = to1d[p][c],to1d[q][c]
  G[v1][v2] = G[v2][v1] = 0
  
for v in range(N):
  if len(to1d[v])>1:
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1
        
def dijkstra(start = 0, goal = 1):
    from heapq import heappop, heappush
    d = [INF]*len(G)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
        if v == goal: return d[goal]
    return d[goal]

for c in to1d[0].keys():
  v = to1d[0][c]
  G[0][v] = 1
for c in to1d[N-1].keys():
  v = to1d[N-1][c]
  G[v][1] = 0
  
ans = dijkstra(0,1)
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 

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

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

INF = 10**20
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

to1d={v:{} for v in range(N)}
count=2
for p,q,c in pqc:
  if not to1d[p].get(c):
    to1d[p][c] = count
    count += 1
  if not to1d[q].get(c):
    to1d[q][c] = count
    count += 1

G = [{} for _ in range(count)]
for p,q,c in pqc:
  v1,v2 = to1d[p][c],to1d[q][c]
  G[v1][v2] = G[v2][v1] = 0
  
for v in range(N):
  if len(to1d[v])>1:
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1
        
def dijkstra(start = 0):
    from heapq import heappop, heappush
    d = [INF]*len(G)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d

for c in to1d[0].keys():
  v = to1d[0][c]
  G[0][v] = 1
for c in to1d[N-1].keys():
  v = to1d[N-1][c]
  G[v][1] = 0
  
d = dijkstra(0)
ans = d[1]
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 

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

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

INF = 10**20
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

to1d={v:{} for v in range(N)}
count=2
for p,q,c in pqc:
  if not to1d[p].get(c):
    to1d[p][c] = count
    count += 1
  if not to1d[q].get(c):
    to1d[q][c] = count
    count += 1

G = [{} for _ in range(count)]
lines = [set() for _ in range(N)]
for p,q,c in pqc:
  v1,v2 = to1d[p][c],to1d[q][c]
  G[v1][v2] = G[v2][v1] = 0
  lines[p].add(c)
  lines[q].add(c)
  
for v in range(N):
  if len(lines[v])>1:
    tmp = list(lines[v])
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1
        
def dijkstra(start = 0):
    from heapq import heappop, heappush
    d = [INF]*len(G)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d

for c in lines[0]:
  v = to1d[0][c]
  G[0][v] = 1
for c in lines[N-1]:
  v = to1d[N-1][c]
  G[v][1] = 0
  
d = dijkstra(0)
ans = d[1]
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict 

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

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

INF = 10**20
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

to1d={}
count=2
for p,q,c in pqc:
  if not to1d.get((p,c)):
    to1d[(p,c)] = count
    count += 1
  if not to1d.get((q,c)):
    to1d[(q,c)] = count
    count += 1

G = [{} for _ in range(len(to1d)+2)]
lines = [set() for _ in range(N)]
for p,q,c in pqc:
  v1,v2 = to1d[(p,c)],to1d[(q,c)]
  G[v1][v2] = G[v2][v1] = 0
  lines[p].add(c)
  lines[q].add(c)
  
for v in range(N):
  if len(lines[v])>1:
    tmp = list(lines[v])
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[(v,tmp[i])],to1d[(v,tmp[j])]
        G[v1][v2] = G[v2][v1] = 1
        
def dijkstra(start = 0):
    from heapq import heappop, heappush
    d = [INF]*len(G)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d

for c in lines[0]:
  v = to1d[(0,c)]
  G[0][v] = 1
for c in lines[N-1]:
  v = to1d[(N-1,c)]
  G[v][1] = 0
  
d = dijkstra(0)
ans = d[1]
print(ans if ans < INF else -1)