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 defaultdict
import heapq

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


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

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

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

        if x == y:
            return

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

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

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


UF = UnionFind(M)
D = {}
E = []
roads = defaultdict(set)


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

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

# UFの親番号をきれいな並び順にする
par_dict = {n: i for i, n in enumerate(sorted(list(set(UF.par))))}
for i in range(M):
    UF.par[i] = par_dict[UF.par[i]]

# 連結した道番号: そこに属している道の辞書をつくる
for i in range(M):
    roads[UF.par[i] + N].add(E[i])

# 属している道->頂点にばらす
for key, edge in roads.items():
    node = set()
    for p, q in edge:
        node.add(p)
        node.add(q)
    roads[key] = node

# 二部グラフ : N番目からが連結した道
if roads.keys():
    G_node_num = max(roads.keys()) + 1
else:
    G_node_num = 1

G = [[] for _ in range(G_node_num)]
for key, nodes in roads.items():
    for node in nodes:
        G[node].append([key, 1])
        G[key].append([node, 1])


def dijkstra(x):
    d = [float('inf')] * max(G_node_num, N)
    d[x] = 0
    visited = {x}

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

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

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


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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def tall(self):
        d = collections.defaultdict(list)
        for i in range(len(self.table)):
            d[self.find(i)].append(i)
        return d

def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for p,q,c in a:
        e[(p,c)].add((q,c))
        e[(q,c)].add((p,c))
        e[(-p,)].add(c)
        e[(-q,)].add(c)
        e[(p,c)].add((-p,))
        e[(q,c)].add((-q,))

    def search():
        d = collections.defaultdict(lambda: inf)
        s = (-1,)
        d[s] = 0
        k = 0
        q = [s]
        nq = []
        v = set()
        while len(q):
            u = q.pop()
            if u in v:
                continue
            v.add(u)
            if u[0] == n:
                return k

            if u[0] < 0:
                for tv in e[u]:
                    uv = (-u[0],tv)
                    if uv in v:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        nq.append(uv)
            else:
                for uv in e[u]:
                    if uv in v:
                        continue
                    vd = k
                    if d[uv] > vd:
                        d[uv] = vd
                        q.append(uv)

            if not q:
                q = nq
                k += 1
                nq = []

        return -1

    return search()



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def tall(self):
        d = collections.defaultdict(list)
        for i in range(len(self.table)):
            d[self.find(i)].append(i)
        return d

def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for p,q,c in a:
        e[(p,c)].add((q,c))
        e[(q,c)].add((p,c))
        e[(-p,)].add((p,c))
        e[(-q,)].add((q,c))
        e[(p,c)].add((-p,))
        e[(q,c)].add((-q,))

    def search():
        d = collections.defaultdict(lambda: inf)
        s = (-1,)
        d[s] = 0
        k = 0
        q = [s]
        nq = []
        v = set()
        while len(q):
            u = q.pop()
            if u in v:
                continue
            v.add(u)
            if u[0] == n:
                return k

            if u[0] < 0:
                for uv in e[u]:
                    if uv in v:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        nq.append(uv)
            else:
                for uv in e[u]:
                    if uv in v:
                        continue
                    vd = k
                    if d[uv] > vd:
                        d[uv] = vd
                        q.append(uv)

            if not q:
                q = nq
                k += 1
                nq = []

        return -1

    return search()



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def tall(self):
        d = collections.defaultdict(list)
        for i in range(len(self.table)):
            d[self.find(i)].append(i)
        return d

def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for p,q,c in a:
        e[(p,c)].add((q,c))
        e[(q,c)].add((p,c))
        e[(-p,)].add((q,c))
        e[(-q,)].add((p,c))
        e[(p,c)].add((-q,))
        e[(q,c)].add((-p,))

    def search():
        d = collections.defaultdict(lambda: inf)
        s = (-1,)
        d[s] = 0
        k = 0
        q = [s]
        nq = []
        v = set()
        while len(q):
            u = q.pop()
            if u in v:
                continue
            v.add(u)
            if u[0] == n:
                return k

            if u[0] < 0:
                for uv in e[u]:
                    if uv in v:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        nq.append(uv)
            else:
                for uv in e[u]:
                    if uv in v:
                        continue
                    vd = k
                    if d[uv] > vd:
                        d[uv] = vd
                        q.append(uv)

            if not q:
                q = nq
                k += 1
                nq = []

        return -1

    return search()



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def tall(self):
        d = collections.defaultdict(list)
        for i in range(len(self.table)):
            d[self.find(i)].append(i)
        return d

def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for p,q,c in a:
        e[(p,c)].add((q,c))
        e[(q,c)].add((p,c))
        e[(-p,)].add((q,c))
        e[(-q,)].add((p,c))
        e[(p,c)].add((-q,))
        e[(q,c)].add((-p,))

    def search():
        d = collections.defaultdict(lambda: inf)
        s = (-1,)
        d[s] = 0
        k = 0
        q = [s]
        nq = []
        v = collections.defaultdict(bool)
        while len(q):
            u = q.pop()
            if v[u]:
                continue
            v[u] = True
            if u[0] == n:
                return k

            if u[0] < 0:
                for uv in e[u]:
                    if v[uv]:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        nq.append(uv)
            else:
                for uv in e[u]:
                    if v[uv]:
                        continue
                    vd = k
                    if d[uv] > vd:
                        d[uv] = vd
                        q.append(uv)

            if not q:
                q = nq
                k += 1
                nq = []

        return -1

    return search()



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def tall(self):
        d = collections.defaultdict(list)
        for i in range(len(self.table)):
            d[self.find(i)].append(i)
        return d

def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for p,q,c in a:
        e[(p,c)].add((q,c))
        e[(q,c)].add((p,c))
        e[(p,-1)].add((q,c))
        e[(q,-1)].add((p,c))
        e[(p,c)].add((q,-1))
        e[(q,c)].add((p,-1))

    def search():
        d = collections.defaultdict(lambda: inf)
        dc = collections.defaultdict(lambda: inf)
        s = (1,-1)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
            if u[0] == n:
                return k
            if dc[u[0]] > k:
                dc[u[0]] = k
            elif dc[u[0]] < k:
                continue

            if u[1] == -1:
                for uv in e[u]:
                    if v[uv]:
                        continue
                    vd = k + 1
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))
            else:
                for uv in e[u]:
                    if v[uv]:
                        continue
                    vd = k
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

        return -1

    return search()



print(main())

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
edgesc = defaultdict(lambda: [])
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))
  edgesc[p, c].append(q)
  edgesc[q, c].append(p)

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = deque([(0, s, -1)])
  while len(que) > 0:
    (d, u, c) = que.popleft()
    if result[u, c] < d:
      continue
    if c < 0:
      for (t, c2) in edges[u]:
        if d + 1 < result[t, c2]:
          result[t, c2] = d + 1
          que.append((d + 1, t, c2))
    else:
      for t in edgesc[u, c]:
        if d < result[t, c2]:
          result[t, c2] = d
          que.appendleft((d, t, c2))
      if d < result[u, -1]:
        result[u, -1] = d
        que.appendleft((d, u, -1))
  return result

dist = dijkstra(edges, 0)
try:
  print(min(d for (u, _), d in dist.items() if u == N-1))
except ValueError:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
# Companies of Station
C_of_S = {}

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


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

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

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


if (M == 0) or not (0 in C_of_S) or not (N-1 in C_of_S):
    print(-1)
    exit()

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

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

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

Submission status: 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 = list(range(M))
def root(x):
	'''
	if x == parent[x]:
		return x
	parent[x] = y = root(parent[x])
	return y
	'''
	return parent[x]
def unite(x, y):
	px = root(x);py = root(y);
	parent[py] = px


#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 collections import deque
import sys
sys.setrecursionlimit(1000000) # 再起呼び出しの最大数をセット
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

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

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	"""
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	"""
	parent[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 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 = list(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);
	parent[py] = px


#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 collections import deque
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

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

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	"""
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	"""
	parent[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 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 = list(range(M))
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py


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

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