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:
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] = i
    E.setdefault(p, set()).add(c)
    if (q, c) in D:
        unite(D[q, c], i)
    D[q, c] = 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 = root(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: Time Limit Exceeded

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] = i
    E.setdefault(p, set()).add(c)
    if (q, c) in D:
        unite(D[q, c], i)
    D[q, c] = 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 < dist[w]:
                dist[w] = cost
                que.appendleft((cost, w, 0))
    else:
        # node
        if dist[v] < cost or v not in E:
            continue
        for c in E[v]:
            w = root(D[v, c])
            if cost + 1 < gdist[w]:
                gdist[w] = cost + 1
                que.append((cost + 1, w, 1))

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

class DijkstraForMStates:

    def get_shortest_path(self, graph, start, state):

        length = len(graph)
        states = len(graph[0])

        distination = [[float("inf") for j in range(states)] for i in range(length)]

        distination[start][state] = 0

        queue = []
        heapq.heappush(queue, (distination[start][state], [start, state]))

        while len(queue):

            previous_cost, source = heapq.heappop(queue)

            if previous_cost > distination[source[0]][source[1]]:
                continue

            for j in range(length):
                for k in range(states):

                    cost = graph[source[0]][source[1]][j][k]

                    if cost != float("inf"):
                        if distination[j][k] > distination[source[0]][source[1]]+cost:
                            distination[j][k] = distination[source[0]][source[1]]+cost
                            heapq.heappush(queue, (distination[j][k], [j, k]))

        return distination

class SubwayTrip:

	def get_shortest_path(self, N, M, pqc):

		graph = [[[[float("inf") for mm in range(M+1)] for nn in range(N)] for m in range(M+1)] for n in range(N)]

		for n in range(N):
			for m in range(1, M+1):
				graph[n][m][n][0] = 1

		for n in range(N):
			for m in range(M+1):
				graph[n][m][n][m] = 0

		for i in pqc:
			graph[i[0]-1][i[2]][i[1]-1][i[2]] = 0
			graph[i[1]-1][i[2]][i[0]-1][i[2]] = 0

			graph[i[0]-1][0][i[1]-1][i[2]] = 0
			graph[i[1]-1][0][i[0]-1][i[2]] = 0

		ans = float("inf")

		D = DijkstraForMStates()

		for m in range(M):
			ans = min(ans, D.get_shortest_path(graph, 0, m)[-1][0])

		print ans if ans != float("inf") else -1

if __name__ == "__main__":

    N, M = [int(i) for i in raw_input().split()]
    pqc  = [[int(j) for j in raw_input().split()] for i in range(M)]

    abc = SubwayTrip()
    abc.get_shortest_path(N, M, pqc)

Submission status: Time Limit Exceeded

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

G = dict()


def add_node(s, Graph=G):
    Graph[s] = {'edges':dict(), 'dist':-1}
    
def add_edge(s, t, weight=1, Graph=G):
    Graph[s]['edges'][t] = weight
    
for i in range(N):
    add_node(str(i+1))
    
for k in range(M):
    p, q, c = map(int, raw_input().split())
    if G.has_key(str([p, c])) == False:
        add_node(str([p, c]))
    if G.has_key(str([q, c])) == False:
        add_node(str([q, c]))
    add_edge(str(p), str([p, c]), 1)
    add_edge(str([p, c]), str(p), 0)
    add_edge(str(q), str([q, c]), 1)
    add_edge(str([q, c]), str(q), 0)
    add_edge(str([p, c]), str([q, c]), 0)
    add_edge(str([q, c]), str([p, c]), 0)
    
# bfs
que = [str(1)]
G[str(1)]['dist'] = 0

while len(que) > 0:
    s = que.pop(0)
    for d in G[s]['edges'].keys():
        if G[d]['dist'] > G[s]['dist'] + G[s]['edges'][d] or G[d]['dist'] == -1:
            G[d]['dist'] = G[s]['dist'] + G[s]['edges'][d]
            que.append(d)

print G[str(N)]['dist']

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
n,m=map(int,input().split())
a=[{} for _ in range(n+1)]
for _ in range(m):
    p,q,c=map(int,input().split())
    a[p].setdefault(c,[])
    a[q].setdefault(c,[])
    a[p][c].append(q)
    a[q][c].append(p)
s=set()
h=[(1,1,c) for c in a[1]]
while True:
    (v,p,c)=heappop(h)
    if p==n:
        break
    if (p,c) in s:
        continue
    s.add((p,c))
    for (d,b) in a[p].items():
        for q in b:
            heappush(h,(v+int(d!=c),q,d))
print(v)

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    p, q, c = map(int, input().split())
    G[(p-1, c-1)].append((p-1, -1))
    G[(q-1, c-1)].append((q-1, -1))
    G[(p-1, -1)].append((p-1, c-1))
    G[(q-1, -1)].append((q-1, c-1))
    G[(p-1, c-1)].append((q-1, c-1))
    G[(q-1, c-1)].append((p-1, c-1))
 
 
dist = defaultdict(lambda :-1)
que = deque([(0, -1)])
dist[(0, -1)] = 0
while que:
    v = que.pop()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]<0:
            if nv[1] == -1:
                dist[nv] = d+1
                que.appendleft(nv)
            else:
                dist[nv] = d
                que.append(nv)
print(dist[(N-1, -1)])

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import deque,defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10**31
N,M = map(int,readline().split())
edges = defaultdict(list)
for i in range(M):
    p,q,c = map(int,readline().split())
    edges[(p,c)].append((q,c))
    edges[(q,c)].append((p,c))
    edges[(p,0)].append((p,c))
    edges[(p,c)].append((p,0))
    edges[(q,0)].append((q,c))
    edges[(q,c)].append((q,0))
    
dist = defaultdict(lambda:-1)
q = deque([(1,0)])
dist[(1,0)] = 0

while q:
    x,c_x = q.popleft()
    d = dist[(x,c_x)]
    for y,c_y in edges[(x,c_x)]:
        if dist[(y,c_y)] < 0:
            if c_y == 0:
                dist[(y,c_y)] = d + 1
                q.append((y,c_y))
            else:
                dist[(y,c_y)] = d 
                q.appendleft((y,c_y))
                
ans = dist[(N,0)]
print(ans if ans != INF else -1)

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import deque,defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10**31
N,M = map(int,readline().split())
edges = defaultdict(list)
for i in range(M):
    p,q,c = map(int,readline().split())
    edges[(p,c)].append((q,c,0))
    edges[(q,c)].append((p,c,0))
    edges[(p,0)].append((p,c,1))
    edges[(p,c)].append((p,0,0))
    edges[(q,0)].append((q,c,1))
    edges[(q,c)].append((q,0,0))
    
dist = defaultdict(lambda:-1)
q = deque([(1,0)])
dist[(1,0)] = 0

while q:
    x,c_x = q.popleft()
    for y,c_y,cost in edges[(x,c_x)]:
        if dist[(y,c_y)] < 0:
            d = dist[(x,c_x)] + cost
            dist[(y,c_y)] = d
            if d == 0:
                q.appendleft((y,c_y))
            else:
                q.append((y,c_y))
ans = dist[(N,0)]
print(ans if ans != INF else -1)

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import deque,defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10**31
N,M = map(int,readline().split())
edges = defaultdict(list)
for i in range(M):
    p,q,c = map(int,readline().split())
    edges[(p,c)].append((q,c,0))
    edges[(q,c)].append((p,c,0))
    edges[(p,0)].append((p,c,1))
    edges[(p,c)].append((p,0,0))
    edges[(q,0)].append((q,c,1))
    edges[(q,c)].append((q,0,0))
    
dist = defaultdict(lambda:INF)
q = deque([(1,0)])
dist[(1,0)] = 0

while q:
    x,c_x = q.popleft()
    for y,c_y,cost in edges[(x,c_x)]:
        d = dist[(x,c_x)] + cost
        if d < dist[(y,c_y)]:
            dist[(y,c_y)] = d
            if d == 0:
                q.appendleft((y,c_y))
            else:
                q.append((y,c_y))
ans = dist[(N,0)]
print(ans if ans != INF else -1)

Submission status: Memory Limit Exceeded

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


def bfs():
    dp[sup_v][0] = 1
    q1 = deque([sup_v])
    q2 = deque([0])
    while q1:
        v1 = q1.popleft()
        v2 = q2.popleft()
        for nxt_v1, nxt_v2 in graph[v1][v2]:
            if nxt_v1 == -1:
                cost = 1
            else:
                cost = 0
            if nxt_v1 not in dp:
                dp[nxt_v1] = {}
            if nxt_v2 not in dp[nxt_v1]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q1.appendleft(nxt_v1)
                    q2.appendleft(nxt_v2)
                else:
                    q1.append(nxt_v1)
                    q2.append(nxt_v2)
            elif dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q1.appendleft(nxt_v1)
                    q2.appendleft(nxt_v2)
                else:
                    q1.append(nxt_v1)
                    q2.append(nxt_v2)
    
n, m = map(int, input().split())
INF = 10 ** 18


sup_v = -1
graph = {sup_v: {0: []}}
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c not in graph:
        graph[c] = {}
    if a not in graph[c]:
        graph[c][a] = []
        graph[c][a].append((sup_v, a))
    if b not in graph[c]:
        graph[c][b] = []
        graph[c][b].append((sup_v, b))
    if a not in graph[sup_v]:
        graph[sup_v][a] = []
    if b not in graph[sup_v]:
        graph[sup_v][b] = []

    graph[c][a].append((c, b))
    graph[c][b].append((c, a))
    graph[sup_v][a].append((c, b))
    graph[sup_v][b].append((c, a))


dp = {sup_v: {}}
bfs()
ans = INF
for i in dp:
    for j in dp[i]:
        if j == n - 1:
            ans = min(dp[i][j], ans)   
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Memory Limit Exceeded

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


def bfs():
    dp[sup_v][0] = 1
    q1 = deque([sup_v])
    q2 = deque([0])
    while q1:
        v1 = q1.popleft()
        v2 = q2.popleft()
        for nxt_v1, nxt_v2 in graph[v1][v2]:
            if nxt_v1 == -1:
                cost = 1
            else:
                cost = 0
            if nxt_v1 not in dp:
                dp[nxt_v1] = {}
            if nxt_v2 not in dp[nxt_v1]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q1.appendleft(nxt_v1)
                    q2.appendleft(nxt_v2)
                else:
                    q1.append(nxt_v1)
                    q2.append(nxt_v2)
            elif dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q1.appendleft(nxt_v1)
                    q2.appendleft(nxt_v2)
                else:
                    q1.append(nxt_v1)
                    q2.append(nxt_v2)
    
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
INF = 10 ** 18


sup_v = -1
graph = {sup_v: {0: []}}
for a, b, c in info:
    a -= 1
    b -= 1
    if c not in graph:
        graph[c] = {}
    if a not in graph[c]:
        graph[c][a] = []
        graph[c][a].append((sup_v, a))
    if b not in graph[c]:
        graph[c][b] = []
        graph[c][b].append((sup_v, b))
    if a not in graph[sup_v]:
        graph[sup_v][a] = []
    if b not in graph[sup_v]:
        graph[sup_v][b] = []

    graph[c][a].append((c, b))
    graph[c][b].append((c, a))
    graph[sup_v][a].append((c, b))
    graph[sup_v][b].append((c, a))


dp = {sup_v: {}}
bfs()
ans = INF
for i in dp:
    for j in dp[i]:
        if j == n - 1:
            ans = min(dp[i][j], ans)   
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Memory Limit Exceeded

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


def bfs():
    dp[sup_v][0] = 1
    q = deque([(sup_v, 0)])
    while q:
        v1, v2 = q.popleft()
        for nxt_v1, nxt_v2 in graph[v1][v2]:
            if nxt_v1 == -1:
                cost = 1
            else:
                cost = 0
            if nxt_v1 not in dp:
                dp[nxt_v1] = {}
            if nxt_v2 not in dp[nxt_v1]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q.appendleft((nxt_v1, nxt_v2))
                else:
                    q.append((nxt_v1, nxt_v2))
            elif dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q.appendleft((nxt_v1, nxt_v2))
                else:
                    q.append((nxt_v1, nxt_v2))
    
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
INF = 10 ** 18


sup_v = -1
graph = {sup_v: {0: []}}
for a, b, c in info:
    a -= 1
    b -= 1
    if c not in graph:
        graph[c] = {}
    if a not in graph[c]:
        graph[c][a] = []
        graph[c][a].append((sup_v, a))
    if b not in graph[c]:
        graph[c][b] = []
        graph[c][b].append((sup_v, b))
    if a not in graph[sup_v]:
        graph[sup_v][a] = []
    if b not in graph[sup_v]:
        graph[sup_v][b] = []

    graph[c][a].append((c, b))
    graph[c][b].append((c, a))
    graph[sup_v][a].append((c, b))
    graph[sup_v][b].append((c, a))


dp = {sup_v: {}}
bfs()
ans = INF
for i in dp:
    for j in dp[i]:
        if j == n - 1:
            ans = min(dp[i][j], ans)   
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Memory Limit Exceeded

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


class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)


def bfs():
    dp[sup_v][0] = 1
    q = deque([(sup_v, 0)])
    while q:
        v1, v2 = q.popleft()
        for nxt_v1, nxt_v2 in graph[v1][v2]:
            if nxt_v1 == -1:
                cost = 1
            else:
                cost = 0
            if nxt_v1 not in dp:
                dp[nxt_v1] = {}
            if nxt_v2 not in dp[nxt_v1]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q.appendleft((nxt_v1, nxt_v2))
                else:
                    q.append((nxt_v1, nxt_v2))
            elif dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q.appendleft((nxt_v1, nxt_v2))
                else:
                    q.append((nxt_v1, nxt_v2))
    
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
INF = 10 ** 18


uf = UnionFind(n)
sup_v = -1
graph = {sup_v: {}}
for a, b, c in info:
    a -= 1
    b -= 1
    if c not in graph:
        graph[c] = {}
    if a not in graph[c]:
        graph[c][a] = []
        graph[c][a].append((sup_v, a))
    if b not in graph[c]:
        graph[c][b] = []
        graph[c][b].append((sup_v, b))
    if a not in graph[sup_v]:
        graph[sup_v][a] = []
    if b not in graph[sup_v]:
        graph[sup_v][b] = []

    graph[c][a].append((c, b))
    graph[c][b].append((c, a))
    graph[sup_v][a].append((c, b))
    graph[sup_v][b].append((c, a))
    uf.merge(a, b)
    
if not uf.is_same(0, n - 1):
    print(-1)
    exit()

dp = {sup_v: {}}
bfs()
ans = INF
for i in dp:
    for j in dp[i]:
        if j == n - 1:
            ans = min(dp[i][j], ans)            
print(ans)

Submission status: Memory Limit Exceeded

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


class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)


def bfs():
    dp[sup_v][0] = 1
    q = deque([(sup_v, 0)])
    while q:
        v1, v2 = q.popleft()
        for nxt_v1, nxt_v2 in graph[v1][v2]:
            if nxt_v1 == -1:
                cost = 1
            else:
                cost = 0
            if dp[v1][v2] + cost < dp[nxt_v1][nxt_v2]:
                dp[nxt_v1][nxt_v2] = dp[v1][v2] + cost
                if cost == 0:
                    q.appendleft((nxt_v1, nxt_v2))
                else:
                    q.append((nxt_v1, nxt_v2))

n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
INF = 10 ** 18


uf = UnionFind(n)
sup_v = -1
graph = {sup_v: {}}
dp = {sup_v: {}}
for a, b, c in info:
    a -= 1
    b -= 1
    if c not in graph:
        graph[c] = {}
        dp[c] = {}
    if a not in graph[c]:
        graph[c][a] = []
        graph[c][a].append((sup_v, a))
        dp[c][a] = INF
    if b not in graph[c]:
        graph[c][b] = []
        graph[c][b].append((sup_v, b))
        dp[c][b] = INF
    if a not in graph[sup_v]:
        graph[sup_v][a] = []
        dp[sup_v][a] = INF
    if b not in graph[sup_v]:
        graph[sup_v][b] = []
        dp[sup_v][b] = INF

    graph[c][a].append((c, b))
    graph[c][b].append((c, a))
    graph[sup_v][a].append((c, b))
    graph[sup_v][b].append((c, a))
    
    uf.merge(a, b)
    
if not uf.is_same(0, n - 1):
    print(-1)
    exit()
    

bfs()
ans = INF
for i in dp:
    for j in dp[i]:
        if j == n - 1:
            ans = min(dp[i][j], ans)            
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    """
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))
    """            
    for tl in g[vl]:
        if tl not in res or res[tl] > dv + (vl&mask==0 or tl&mask==0):
            res[tl] = dv + (vl&mask==0 or tl&mask==0)
            if vl&mask==0 or tl&mask==0:
                q.append((tl,dv + (vl&mask==0 or tl&mask==0)))
            else:
                q.appendleft((tl,dv + (vl&mask==0 or tl&mask==0)))

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1: res[(n-1)<<20] = dv+1; break

    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))
            

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([0])
res = {0:0}

mask = (1<<20)-1
while q:
    vldv = q.popleft()
    vl,dv = vldv>>20, vldv&mask
    if res[vl] < dv: continue
    if vl==(n-1)<<20: break

    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl<<20)+ndv)
            else:
                q.appendleft((tl<<20)+ndv)
            

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([0])
res = {0:0}

mask = (1<<20)-1
INF = 1<<29
while q:
    vldv = q.popleft()
    vl,dv = vldv>>20, vldv&mask
    if res[vl] < dv: continue
    #if vl==(n-1)<<20: break

    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.appendleft((tl<<20)+ndv)
            else:
                q.append((tl<<20)+ndv)
            

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g : g[pp] = []
    if qq not in g : g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)


    
from collections import deque

q = deque([(0,0)])
res = {0:0}
mask = (1<<20)-1
INF = 1<<30

if 0 not in g: g[0] = []
#print(res)
while q:
    #print(q)
    vl,dv = q.popleft()
    if res[vl] < dv: continue

    v,l = vl>>20, vl&mask
    for tl in g[vl]:
        to = tl>>20
        line = tl&mask
        cost = (l==0 or line==0)
        ndv = cost + dv
        if (tl not in res or res[tl] > ndv):
            res[tl] = ndv
            if cost: q.appendleft((tl,ndv))
            else: q.append((tl,ndv))
            

if (n-1)<<20 in res: x = res[(n-1)<<20]; print(x//2)
else: print(-1)

Submission status: Memory Limit Exceeded

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

n, m = map(int, input().split())
G = defaultdict(set)
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[(p, c)].add(((q, c), 0))
  G[(q, c)].add(((p, c), 0))
  G[(p, c)].add(((p, -1), 0))
  G[(q, c)].add(((q, -1), 0))
  G[(p, -1)].add(((p, c), 1))
  G[(q, -1)].add(((q, c), 1))
que = deque()
que.append(((1, -1), 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == (n, -1):
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)