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:
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():
    M = 2**20
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for p,q,c in a:
        e[p+c*M].add(q+c*M)
        e[q+c*M].add(p+c*M)
        e[p-M].add(p+c*M)
        e[q-M].add(q+c*M)
        e[p+c*M].add(p-M)
        e[q+c*M].add(q-M)

    def search():
        d = collections.defaultdict(lambda: inf)
        s = 1-M
        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:
                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:
                if u % M == n:
                    return k

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

        return -1

    return search()



print(main())

Submission status: Time Limit Exceeded

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():
    M = 2**20
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for p,q,c in a:
        e[p+c*M].add((q+c*M, 0))
        e[q+c*M].add((p+c*M, 0))
        e[p-M].add((p+c*M, 1))
        e[q-M].add((q+c*M, 1))
        e[p+c*M].add((p-M, 0))
        e[q+c*M].add((q-M, 0))

    def search():
        d = collections.defaultdict(lambda: inf)
        s = 1-M
        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 % M == n:
                return k

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

        return -1

    return search()



print(main())

Submission status: Time Limit Exceeded

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():
    M = 2**20
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for p,q,c in a:
        e[p*M+c].add((q*M+c, 0))
        e[q*M+c].add((p*M+c, 0))
        e[p*M-1].add((p*M+c, 1))
        e[q*M-1].add((q*M+c, 1))
        e[p*M+c].add((p*M-1, 0))
        e[q*M+c].add((q*M-1, 0))

    def search():
        d = collections.defaultdict(lambda: inf)
        s = M-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 // M == n:
                return k

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

        return -1

    return search()



print(main())

Submission status: Time Limit Exceeded

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
        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 u[0] < 0:
                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: Time Limit Exceeded

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

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), 0))
        e[(q,c)].add(((p,c), 0))
        e[(p,-1)].add(((q,c), 1))
        e[(q,-1)].add(((p,c), 1))
        e[(p,c)].add(((q,-1), 0))
        e[(q,c)].add(((p,-1), 0))

    def search():
        d = 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

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

        return -1

    return search()



print(main())

Submission status: Time Limit Exceeded

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)


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

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

            for uv, uc in e[u[0]]:
                if v[(uv,uc)]:
                    continue
                vd = k
                if uc != c:
                    vd += 1
                if d[(uv,uc)] > vd and d[uv] >= vd:
                    d[(uv,uc)] = vd
                    d[uv] = vd
                    heapq.heappush(q, (vd, (uv,uc)))

        return -1

    return search()


print(main())

Submission status: Time Limit Exceeded

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)


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

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

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

        return -1

    return search()


print(main())

Submission status: Time Limit Exceeded

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)]
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))

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, c2) in edges[u]:
        if c == c2 and 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: Time Limit Exceeded

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)]
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))

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
    for (t, c2) in edges[u]:
      cost = 0 if c == c2 else 1
      if d + cost < result[t, c2]:
        result[t, c2] = d + cost
        if cost == 0:
          que.appendleft((d + cost, t, c2))
        else:
          que.append((d + cost, t, c2))
  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: Time Limit Exceeded

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)]
for _ in range(M):
  p, q, c = reads()
  p, q = p-1, q-1
  edges[p].append((q, c))
  edges[q].append((p, c))

INF = 1 << 30
def dijkstra(edges, s):
  result = defaultdict(lambda: INF)
  result[s, -1] = 0
  que = [(0, s, -1)]
  while len(que) > 0:
    (d, u, c) = heappop(que)
    if result[u, c] < d: continue
    for (t, c2) in edges[u]:
      cost = int(c != c2)
      if d + cost < result[t, c2]:
        result[t, c2] = d + cost
        heappush(que, (d + cost, t, c2))
  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: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq

def dijkstra(graph, start, end):
    q = []
    heapq.heapify(q)
    visited = set()

    for next_, cost in graph[start].items():
        heapq.heappush(q, (cost, next_))

    while len(q) > 0:
        node_cost, current = heapq.heappop(q)
        if current in visited:
            continue
        if current == end:
            return node_cost

        visited.add(current)
        for next_, path_cost in graph[current].items():
            heapq.heappush(q, (node_cost + path_cost, next_))

    return -1

n, m = map(int, input().split())
pqcs = [tuple(map(int, input().split())) for _ in range(m)]

graph = defaultdict(dict)

for p, q, c in pqcs:
    graph[(p, c)][(q, c)] = 0
    graph[(q, c)][(p, c)] = 0
    graph[(p, -1)][(p, c)] = 1
    graph[(p, c)][(p, -1)] = 0
    graph[(q, -1)][(q, c)] = 1
    graph[(q, c)][(q, -1)] = 0

print(dijkstra(graph, (1, -1), (n, -1)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
Q = {0:deque([1])}
distance = {1:0}

#辺へ重み付け
edges = {}
for p,q,c in pqcs:
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

flag = False
while 1:
	for i in range(len(Q)):                            
		if not (Q[i]):
			continue
		flag = True
		target_min_ind = Q[i].popleft()
		target_node = edges[target_min_ind]
		break
	if not (flag):
		break

	for key, value in target_node.items():
		distance.setdefault(key, float('inf'))
		dist = distance[target_min_ind] + value
		if distance[key] > dist:
			distance[key] = dist
			Q.setdefault(dist, deque())
			Q[dist].append(key)
		if key == N:
			flag = False
	if not (flag):
		break

print(distance[N] if distance[N] != float('inf') else -1)
exit()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearched_nodes = [c*10**6+s+1 for s in range(N) for c in range(c_max+1)]
#opt_nodes = [-1]*node_num
distance = {1:0}
#辺へ重み付け
edges = {}
for p,q,c in pqcs:
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

while not (distance.get(N)):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearched_nodes:
    	if (distance.get(unsearched_ind) != None):
    		if temp_min_dist > distance[unsearched_ind]:
    			temp_min_dist = distance[unsearched_ind]
    			target_min_ind = unsearched_ind
    unsearched_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
   
    for key, value in target_node.items():
    	distance.setdefault(key, float('inf'))
    	if distance[key] > distance[target_min_ind] + value:
    		distance[key] = distance[target_min_ind] + value
    	if key == N:
    		print(distance[N] if distance[N] != float('inf') else -1)
    		exit()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
#unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
unsearched_nodes = [c*10**6+s+1 for s in range(N) for c in range(c_max+1)]
#opt_nodes = [-1]*node_num
#distance = [float('inf')]*node_num
#distance[0] = 0
distance = {c*10**6+s+1: float('inf') for s in range(N) for c in range(c_max+1)}
distance[1] = 0
#edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
edges = {}
for p,q,c in pqcs:
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

while (distance[N] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearched_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    #if temp_min_dist == float('inf'):
        #break
    unsearched_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
   
    for key, value in target_node.items():
    	if distance[key] > distance[target_min_ind] + value:
    		distance[key] = distance[target_min_ind] + value
    		#opt_nodes[key] = target_min_ind

print(distance[N] if distance[N] != float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
routes = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
#print(routes)

# i駅まで到達したときの最小コスト（最終電車がjで示される）
dp = [{} for _ in range(N + 1)]
dp[1][0] = 0

for i in range(2, N + 1):
    for (f, t, m) in routes:
        if t != i:
            continue

        if m in dp[f]:
            dp[t][m] = dp[f][m]
        else:
            values = []
            for k, v in dp[f].items():
                if k != m: values.append(v)
            if len(values) > 0:
                dp[t][m] = min(values) + 1

if len(dp[N].values()) > 0:
    print(min(dp[N].values()))
else:
    print(-1)