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

Solution code:
class UnionFindVerSize():
    def __init__(self,init):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, len(init))]
        # グループのサイズ（個数）
        self._size = [1] * len(init)
        self._dict ={key:0 for key in init}
        for i in range(len(init)):
            v=init[i]
            self._dict[v]=i

    def find_root(self, x,key):
        """ xの木の根(xがどのグループか)を求める """
        if key==1:
            x=self._dict[x]
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x],0) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        x=self._dict[x]
        y=self._dict[y]
        gx = self.find_root(x,0)
        gy = self.find_root(y,0)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        x=self._dict[x]
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x,0)]

    def is_same_group(self, x, y):
        x=self._dict[x]
        y=self._dict[y]
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x,0) == self.find_root(y,0)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i,0) == i:
                ans += 1
        return ans

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
company={}
cedge={}
node=N
edge=[]
for i in range(M):
    u,v,c=map(int,input().split())
    edge.append((u-1,v-1,1))
    edge.append((v-1,u-1,1))
    if c-1 not in company:
        company[c-1]=[]
        cedge[c-1]=[]
    company[c-1].append(u-1)
    company[c-1].append(v-1)
    cedge[c-1].append((u-1,v-1))

for i in company:
    uf=UnionFindVerSize(company[i])
    for u,v in cedge[i]:
        uf.unite(u,v)
    data={}
    for v in company[i]:
        p=uf.find_root(v,1)
        if p not in data:
            data[p]=[]
        data[p].append(v)
    for p in data:
        for v in data[p]:
            edge.append((v,node,0))
            edge.append((node,v,1))
        node+=1

station=Dijkstra(node)
for u,v,c in edge:
    station.add(u,v,c)

ans=station.shortest_path(0)[N-1]
print(ans if ans!=10**15 else -1)

Submission status: Memory Limit Exceeded

Solution code:
class UnionFindVerSize():
    def __init__(self,init):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, len(init))]
        # グループのサイズ（個数）
        self._size = [1] * len(init)
        self._dict ={key:0 for key in init}
        for i in range(len(init)):
            v=init[i]
            self._dict[v]=i

    def find_root(self, x,key):
        """ xの木の根(xがどのグループか)を求める """
        if key==1:
            x=self._dict[x]
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x],0) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        x=self._dict[x]
        y=self._dict[y]
        gx = self.find_root(x,0)
        gy = self.find_root(y,0)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        x=self._dict[x]
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x,0)]

    def is_same_group(self, x, y):
        x=self._dict[x]
        y=self._dict[y]
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x,0) == self.find_root(y,0)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i,0) == i:
                ans += 1
        return ans

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
company=[[] for i in range(10**6)]
cedge=[[] for i in range(10**6)]
node=N
edge=[]
for i in range(M):
    u,v,c=map(int,input().split())
    edge.append((u-1,v-1,1))
    edge.append((v-1,u-1,1))
    company[c-1].append(u-1)
    company[c-1].append(v-1)
    cedge[c-1].append((u-1,v-1))

for i in range(10**6):
    if company[i]:
        uf=UnionFindVerSize(company[i])
        for u,v in cedge[i]:
            uf.unite(u,v)
        data={}
        for v in company[i]:
            p=uf.find_root(v,1)
            if p not in data:
                data[p]=[]
            data[p].append(v)
        for p in data:
            for v in data[p]:
                edge.append((v,node,0))
                edge.append((node,v,1))
            node+=1

station=Dijkstra(node)
for u,v,c in edge:
    station.add(u,v,c)

ans=station.shortest_path(0)[N-1]
print(ans if ans!=10**15 else -1)

Submission status: Memory Limit Exceeded

Solution code:
def resolve():
    def Dijkstra(s, g):
        from collections import deque
        d = {s}
        queue = deque()
        for q in edge[s]:
            queue.append((1, q))
        while queue:
            dist, point = queue.popleft()
            if point in d:
                continue
            d.add(point)
            if point == g:
                return dist
            for nextp in edge[point]:
                if not nextp in d:
                    if not -1 in point or -1 in nextp:
                        queue.appendleft((dist, nextp))
                    else:
                        queue.append((dist + 1, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, c)].add((q, c))
        edge[(q, c)].add((p, c))
        edge[(p, c)].add((p, -1))
        edge[(q, c)].add((q, -1))
        edge[(p, -1)].add((p, c))
        edge[(q, -1)].add((q, c))
    print(Dijkstra((0, -1), (n - 1, -1)))


if __name__ == '__main__':
    resolve()

Submission status: Memory Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
inf = 10**9+7
def dijkstra(N, s, Edge):    
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dn + df < dist[vf]:
                dist[vf] = dn + df
                hp(Q, (dn + df,vf))
    return dist

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


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

Edge = []
VS = set(range(N))
geta = 20
Edge = [tuple(map(int, readline().split())) for _ in range(M)]
for a, b, c in Edge:
    a -= 1
    b -= 1
    VS |= {(c<<geta) | a, (c<<geta) | b}
   
_, Cv = compress(list(VS))

Vnum = len(Cv)

nEdge = [[] for _ in range(Vnum)]

for a, b, c in Edge:
    a -= 1
    b -= 1
    ca = Cv[(c<<geta) | a]
    cb = Cv[(c<<geta) | b]
    nEdge[ca].append((0, cb))
    nEdge[cb].append((0, ca))
    nEdge[a].append((1, ca))
    nEdge[ca].append((0, a))
    nEdge[b].append((1, cb))
    nEdge[cb].append((0, b))

dist = dijkstra(Vnum, 0, nEdge)
if dist[N-1] >= inf:
    dist[N-1] = -1
print(dist[N-1])

Submission status: Memory Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
inf = 10**9+7
def dijkstra(N, s, Edge):    
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    dp = [0]*N
    dp[s] = 1
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dn + df < dist[vf]:
                dist[vf] = dn + df
                dp[vf] = dp[vn]
                hp(Q, (dn + df,vf))
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn])
    return dist, dp

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


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

Edge = []
VS = set(range(N))
geta = 20
Edge = [tuple(map(int, readline().split())) for _ in range(M)]
for a, b, c in Edge:
    a -= 1
    b -= 1
    VS |= {(c<<geta) | a, (c<<geta) | b}
   
_, Cv = compress(list(VS))

Vnum = len(Cv)

nEdge = [[] for _ in range(Vnum)]

for a, b, c in Edge:
    a -= 1
    b -= 1
    ca = Cv[(c<<geta) | a]
    cb = Cv[(c<<geta) | b]
    nEdge[ca].append((0, cb))
    nEdge[cb].append((0, ca))
    nEdge[a].append((1, ca))
    nEdge[ca].append((0, a))
    nEdge[b].append((1, cb))
    nEdge[cb].append((0, b))

dist, _ = dijkstra(Vnum, 0, nEdge)
if dist[N-1] >= inf:
    dist[N-1] = -1
print(dist[N-1])

Submission status: Memory Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
inf = 10**9+7
def dijkstra(N, s, Edge):    
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    dp = [0]*N
    dp[s] = 1
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dn + df < dist[vf]:
                dist[vf] = dn + df
                dp[vf] = dp[vn]
                hp(Q, (dn + df,vf))
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn])
    return dist, dp

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


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

Edge = []
VS = list(range(N))
geta = 20
for _ in range(M):
    a, b, c = map(int, readline().split())
    a -= 1
    b -= 1
    Edge.append(((c<<geta) | a, (c<<geta) | b, 0))
    Edge.append(((c<<geta) | a, a, 1))
    Edge.append(((c<<geta) | b, b, 1))
    VS.extend([(c<<geta) | a, (c<<geta) | b])
    
    
_, Cv = compress(VS)

Vnum = len(Cv)

nEdge = [[] for _ in range(Vnum)]

for a, b, c in Edge:
    ca = Cv[a]
    cb = Cv[b]
    nEdge[ca].append((0, cb))
    nEdge[cb].append((c, ca))

dist, _ = dijkstra(Vnum, 0, nEdge)
if dist[N-1] >= inf:
    dist[N-1] = -1
print(dist[N-1])

Submission status: Memory Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,M = map(int,readline().split())
if M == 0:
    print(-1)
    exit()
m = map(int,read().split())
P,Q,C = zip(*zip(m,m,m))

V = []
V += [p<<32 for p in range(1,N+1)]
V += [(p<<32)+c for p,c in zip(P,C)]
V += [(q<<32)+c for q,c in zip(Q,C)]
V = set(V)
label = {x:i for i,x in enumerate(V)}
start = label[1<<32]
goal = label[N<<32]

N = len(V)
graph = [[] for _ in range(N)]
for p,q,c in zip(P,Q,C):
    v0 = label[p<<32]; v1 = label[(p<<32)+c]
    w0 = label[q<<32]; w1 = label[(q<<32)+c]
    graph[v0].append((v1,1))
    graph[w0].append((w1,1))
    graph[v1].append((v0,0))
    graph[w1].append((w0,0))
    graph[v1].append((w1,0))
    graph[w1].append((v1,0))

INF = 10 ** 10
dist = [INF] * N
dist[start] = 0
q = deque([(0,start)])
while q:
    dv,v = q.popleft()
    for w,cost in graph[v]:
        dw = dv + cost
        if dw >= dist[w]:
            continue
        dist[w] = dw
        if not cost:
            q.appendleft((dw,w))
        else:
            q.append((dw,w))

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)

Submission status: Memory Limit Exceeded

Solution code:
import sys,heapq
from collections import defaultdict,deque

input = sys.stdin.readline
n,m = map(int,input().split())
#+路線*chg : その路線ホーム
chg = 10**6

edge=defaultdict(set)
used =defaultdict(bool)
for i in range(m):
    p,q,c = map(int,input().split())
    edge[p].add(p+c*chg)
    edge[p+c*chg].add(p)
    edge[p+c*chg].add(q+c*chg)
    edge[q+c*chg].add(p+c*chg)
    edge[q].add(q+c*chg)
    edge[q+c*chg].add(q)
    used[p] = False
    used[q] = False
    used[p+c*chg] = False
    used[q+c*chg] = False

edgelist = deque()
edgelist.append((1,0))
res = float("inf")

while len(edgelist):
    x,cost = edgelist.pop()
    used[x] = True

    if x == n:
        res = cost
        break
    for e in edge[x]:
        if used[e]:
            continue
        #ホーム→改札
        if x <= 10**5 and chg <= e:
            edgelist.appendleft((e,cost+1))
        else:
            edgelist.append((e,cost))
        
if res == float("inf"):
    print(-1)
else:
    print(res)

Submission status: Memory 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)

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

ans = -1

while que:
    (cost, (cur, comp)) = que.popleft()
    
    if (cur,comp) in visited:
        continue
    
    elif cur == n:
        ans = cost
        break
    
    visited.add((cur, comp))
    
    
    for (nextstat, nextcomp) in graph[(cur, comp)]:
        if (nextstat, nextcomp) in visited:
            continue
        
        elif comp == 0:
            que.append((cost+1, (nextstat, nextcomp)))
            
        else:
            que.appendleft((cost, (nextstat, nextcomp)))
    
print(ans)

Submission status: Memory 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 collections import defaultdict, deque

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

for _ in range(m):
    p,q,c = li()
    
    graph[(p, c)].add((q, c))
    graph[(q, c)].add((p, c))
    
    graph[(p, c)].add((p, 0))
    graph[(q, c)].add((q, 0))
    
    graph[(p, 0)].add((p, c))
    graph[(q, 0)].add((q, c))
    
INF = 1<<62
que = deque()
que.append((0, (1, 0)))
visited = defaultdict(int)

ans = -1

while que:
    (cost, (cur, comp)) = que.popleft()
    
    if visited[(cur,comp)]:
        continue
    
    elif cur == n:
        ans = cost
        break
    
    visited[(cur, comp)] = True
    
    
    for (nextstat, nextcomp) in graph[(cur, comp)]:
        if visited[(nextstat, nextcomp)]:
            continue
        
        elif comp == 0:
            que.append((cost+1, (nextstat, nextcomp)))
            
        else:
            que.appendleft((cost, (nextstat, nextcomp)))
    
print(ans)

Submission status: Memory 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 collections import defaultdict, deque

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

for _ in range(m):
    p,q,c = li()
    
    graph[(p, c)].add((0, (q, c)))
    graph[(q, c)].add((0, (p, c)))
    
    graph[(p, c)].add((0, (p, 0)))
    graph[(q, c)].add((0, (q, 0)))
    
    graph[(p, 0)].add((1, (p, c)))
    graph[(q, 0)].add((1, (q, c)))
    
INF = 1<<62
que = deque()
que.append((0, (1, 0)))
visited = defaultdict(int)

ans = -1

while que:
    (cost, (cur, comp)) = que.popleft()
    
    if visited[(cur,comp)]:
        continue
    
    elif cur == n:
        ans = cost
        break
    
    visited[(cur, comp)] = True
    
    
    for (nextcost, (nextstat, nextcomp)) in graph[(cur, comp)]:
        if visited[(nextstat, nextcomp)]:
            continue
        
        elif nextcost == 1:
            que.append((cost+1, (nextstat, nextcomp)))
            
        else:
            que.appendleft((cost, (nextstat, nextcomp)))
    
print(ans)

Submission status: Memory 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

def dijkstra(graph: list, 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 = [[] for _ in [0]*(5*(10**5))]
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].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))
    
INF = 1<<62
start = get_nodenum(1, 0, keyset, node2num)

graph = graph[:len(node2num)]

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: Memory 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

def dijkstra(graph: list, 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 = [[] for _ in [0]*(5*(10**5))]
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].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))
    
INF = 1<<62
start = get_nodenum(1, 0, keyset, node2num)

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: Memory 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):
    d = {}
    for v in g.keys():
        d[v] = sys.maxsize
    d[s] = 0

    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
                if g[u][v] == 0:
                    q.appendleft((d[v], v))
                else:
                    q.append((d[v], v))
    return d


@mt
def slv(N, M):

    g = defaultdict(dict)
    NM = 30
    for _ in range(M):
        p, q, c = input().split()
        p = int(p)
        q = int(q)
        c = int(c)

        cp = (c << NM) + p
        cq = (c << NM) + q
        g[cp][cq] = 0
        g[cq][cp] = 0
        g[cp][p] = 0
        g[cq][q] = 0
        g[p][cp] = 1
        g[q][cq] = 1

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


def main():
    N, M = read_int_n()

    print(slv(N, M))


if __name__ == '__main__':
    main()

Submission status: Memory 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):
    d = {}
    for v in g.keys():
        d[v] = sys.maxsize
    d[s] = 0

    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
                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)
    NM = 30
    for p, q, c in PQC:
        cp = (c << NM) + p
        cq = (c << NM) + q
        g[cp][cq] = 0
        g[cq][cp] = 0
        g[cp][p] = 0
        g[cq][q] = 0
        g[p][cp] = 1
        g[q][cq] = 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()