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:
def resolve():
    def Dijkstra(s, g):
        import heapq
        d = {}
        d[s] = 0
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            if point in d:
                continue
            d[point] = dist
            if point == g:
                return dist
            for nextdist, nextp in edge[point]:
                if not nextp in d:
                    heapq.heappush(queue, (dist + nextdist, 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, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print(Dijkstra((0, -1), (n - 1, -1)))


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def Dijkstra(s, g, edge, inf=float("inf")):
        import heapq
        d = {}
        d[s] = 0
        used = set()
        used.add(s)
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            if point in used:
                continue
            d[point] = dist
            if point == g:
                return dist
            used.add(point)
            for nextdist, nextp in edge[point]:
                if not nextp in used:
                    heapq.heappush(queue, (dist + nextdist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    inf = 10 ** 10
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print(Dijkstra((0, -1), (n - 1, -1), edge, inf))


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:

"""

Writer: SPD_9X2
https://atcoder.jp/contests/arc061/tasks/arc061_c
拡張ダイクストラ？

両端に繋ぐので高々M*2頂点にしかならない
dis[駅]{会社} = 頂点番号index
ps[ind] = 駅
で置いておくのがいいか
あとは駅が同じ頂点同士を結ぶ
相互に結ぶとやばそうなので分割しちゃう
indexに駅番号を付けておけば解決

"""

from collections import deque
import heapq
N,M = map(int,input().split())

lis = [{} for i in range(N)]
ps = []
link = []
dis = []
que = []

for loop in range(M):

    p,q,c = map(int,input().split())

    p -= 1
    q -= 1
    c -= 1

    if c not in lis[p]:
        ind1 = len(ps)
        ps.append(p)
        link.append([])
        lis[p][c] = ind1
        if p == 0:
            dis.append(1)
            heapq.heappush(que,[1,ind1])
        else:
            dis.append(float("inf"))
    else:
        ind1 = lis[p][c]

    if c not in lis[q]:
        ind2 = len(ps)
        ps.append(q)
        lis[q][c] = ind2
        link.append([])
        if q == 0:
            dis.append(1)
            heapq.heappush(que,[1,ind2])
        else:
            dis.append(float("inf"))
    else:
        ind2 = lis[q][c]

    link[ind1].append(ind2)
    link[ind2].append(ind1)

able = [True] * len(dis)
rem = len(dis)

while len(que) > 0 and rem > 0:

    tmp = heapq.heappop(que)
    score,now = tmp

    if not able[now]:
        continue
    able[now] = False
    rem -= 1

    for nex in link[now]:
        if dis[nex] > dis[now]:
            dis[nex] = dis[now]
            heapq.heappush(que,[dis[nex],nex])

    for ni in lis[ps[now]]:
        nex = lis[ps[now]][ni]

        if dis[nex] > dis[now] + 1:
            dis[nex] = dis[now] + 1
            heapq.heappush(que,[dis[nex],nex])

ans = float("inf")
for i in range(len(ps)):

    if ps[i] == N-1:
        ans = min(ans , dis[i])

#print (ps)
#print (dis)
if ans == float("inf"):
    print (-1)
else:
    print (ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = 1000000000


def dijkstra(G, d, s):
    h = []
    d[s] = 0
    heapq.heappush(h, (0, s))

    while len(h) != 0:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in G[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(h, (d[e[0]], e[0]))


def main():
    N, M = map(int, input().split())
    p = [0] * M
    q = [0] * M
    c = [0] * M
    for i in range(M):
        p[i], q[i], c[i] = map(int, input().split())
        p[i] -= 1
        q[i] -= 1
    plat = []
    for i in range(N):
        plat.append(dict())
    v_count = 0
    for i in range(M):
        p1 = plat[p[i]]
        if not c[i] in p1:
            p1[c[i]] = v_count
            v_count += 1
        p2 = plat[q[i]]
        if not c[i] in p2:
            p2[c[i]] = v_count
            v_count += 1
    for i in range(N):
        plat[i][-1] = v_count
        v_count += 1

    G = [[] for _ in range(v_count)]
    for i in range(M):
        p1 = plat[p[i]][c[i]]
        q1 = plat[q[i]][c[i]]
        G[p1].append((q1, 0))
        G[q1].append((p1, 0))
    for i in range(N):
        out = plat[i][-1]
        for v in plat[i].values():
            if v == -1:
                continue
            G[v].append((out, 0))
            G[out].append((v, 1))

    start = plat[0][-1]
    goal = plat[N - 1][-1]

    d = [INF for _ in range(v_count)]

    dijkstra(G, d, start)

    if d[goal] == INF:
        print(-1)
    else:
        print(d[goal])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

N, M = map(int, input().split())
INF = 10**18

edges = defaultdict(set)
C = set()
for _ in range(M):
    fr, to, c = map(int, input().split())
    edges[(fr, c)].add((to, c, 0))
    edges[(to, c)].add((fr, c, 0))

    edges[(fr, c)].add((fr, -1, 0))
    edges[(to, c)].add((to, -1, 0))

    edges[(fr, -1)].add((fr, c, 1))
    edges[(to, -1)].add((to, c, 1))
    C.add(c)

minDist = defaultdict(lambda: INF)
minDist[(1, -1)] = 0
que = [(0, 1, -1)]

while que:
    dist, now, c = heappop(que)

    for to, c, d in edges[(now, c)]:
        if minDist[(to, c)] > dist + d:
            minDist[(to, c)] = dist + d
            heappush(que, (dist + d, to, c))

ans = INF
for c in C:
    ans = min(ans, minDist[(N, c)])
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

N, M = map(int, input().split())
INF = 10**18

edges = defaultdict(list)
C = set()
for _ in range(M):
    fr, to, c = map(int, input().split())
    edges[(fr, c)].append((to, c, 0))
    edges[(to, c)].append((fr, c, 0))

    edges[(fr, c)].append((fr, -1, 0))
    edges[(to, c)].append((to, -1, 0))

    edges[(fr, -1)].append((fr, c, 1))
    edges[(to, -1)].append((to, c, 1))
    C.add(c)

minDist = defaultdict(lambda: INF)
minDist[(1, -1)] = 0
que = [(0, 1, -1)]

while que:
    dist, now, c = heappop(que)

    for to, c, d in edges[(now, c)]:
        if minDist[(to, c)] > dist + d:
            minDist[(to, c)] = dist + d
            heappush(que, (dist + d, to, c))

ans = INF
for c in C:
    ans = min(ans, minDist[(N, c)])
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

N, M = map(int, input().split())
INF = 10**18

edges = defaultdict(list)
for _ in range(M):
    fr, to, c = map(int, input().split())
    edges[(fr, c)].append((to, c, 0))
    edges[(to, c)].append((fr, c, 0))

    edges[(fr, c)].append((fr, -1, 0))
    edges[(to, c)].append((to, -1, 0))

    edges[(fr, -1)].append((fr, c, 1))
    edges[(to, -1)].append((to, c, 1))

minDist = defaultdict(lambda: INF)
que = [(0, 1, -1)]

while que:
    dist, now, c = heappop(que)

    for to, c, d in edges[(now, c)]:
        if minDist[(to, c)] > dist + d:
            minDist[(to, c)] = dist + d
            heappush(que, (dist + d, to, c))

ans = INF
for (v, _), d in minDist.items():
    if v == N and ans > d:
        ans = d
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
n,m = map(int, input().split())
link = defaultdict(list)
chg=10**8
for _ in range(m):
    p,q,c=map(int, input().split())
    link[p].append([p+chg*c,1])
    link[p+chg*c].append([p,1])

    link[q+chg*c].append([p+chg*c,0])
    link[p+chg*c].append([q+chg*c,0])

    link[q+chg*c].append([q,1])
    link[q].append([q+chg*c,1])

def dks(g,start):
    INF=float('inf')
    visited = defaultdict(int)
    hq = []
    heappush(hq, (0,start))
    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if visited[i] != 0:
            continue
        visited[i] = 1
        cost[i] = shortest
        for j, t in g[i]:
            if visited[j] != 0:
                continue
            heappush(hq, (shortest + t, j))
    return cost
cost=dks(link,1)

ans=cost[n]
if ans == float("inf"):
    print(-1)
else:
    print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m = map(int, input().split())
pqc=[list(map(int,input().split())) for i in range(m)]
from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
def dks(g,start):
    INF=float('inf')
    visited = defaultdict(int)
    hq = []
    heappush(hq, (0,start))
    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if visited[i] != 0:
            continue
        visited[i] = 1
        cost[i] = shortest
        for j, t in g[i]:
            if visited[j] != 0:
                continue
            heappush(hq, (shortest + t, j))
    return cost

link = defaultdict(list)
for tmp in pqc:
    p,q,c=tmp
    p-=1
    q-=1
    c-=1
    link[(p,-1)].append([(p,c),1])
    link[(p,c)].append([(p,-1),1])
    link[(p,c)].append([(q,c),0])
    link[(q,c)].append([(p,c),0])
    link[(q,-1)].append([(q,c),1])
    link[(q,c)].append([(q,-1),1])

cost=dks(link,(0,-1))
ans=cost[n-1,-1]
if ans == float("inf"):
    print(-1)
else:
    print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
pqc=[list(map(int,input().split())) for i in range(m)]

from collections import defaultdict
from heapq import heappush, heappop,heappushpop,heapify
def dks(g,start):
    INF=float('inf')
    visited = defaultdict(int)
    hq = []
    heappush(hq, (0,start))
    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if visited[i] != 0:
            continue
        visited[i] = 1
        cost[i] = shortest
        for j, t in g[i]:
            if visited[j] != 0:
                continue
            heappush(hq, (shortest + t, j))
    return cost

link = defaultdict(list)
for tmp in pqc:
    p,q,c=tmp
    p-=1
    q-=1
    c-=1
    link[(p,-1)].append([(p,c),1])
    link[(p,c)].append([(p,-1),1])
    link[(p,c)].append([(q,c),0])
    link[(q,c)].append([(p,c),0])
    link[(q,-1)].append([(q,c),1])
    link[(q,c)].append([(q,-1),1])

cost=dks(link,(0,-1))
ans=cost[n-1,-1]
if ans == float("inf"):
    print(-1)
else:
    print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque
INF = 10**9

n, m = map(int, input().split())
pqc = []

seen = set()
for i in range(n):
    seen.add((i, 0))
for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1
    pqc.append((p, q, c))
    seen.add((p, c))
    seen.add((q, c))
comp = dict()
for i, node in enumerate(seen):
    comp[node] = i

edge = [[] for _ in range(len(comp))]
for key in comp.keys():
    v, c = key
    if c != 0:
        frm = comp[(v, c)]
        too = comp[(v, 0)]
        edge[frm].append((too, 0))
        edge[too].append((frm, 1))

for p, q, c in pqc:
    frm = comp[(p, c)]
    too = comp[(q, c)]
    edge[frm].append((too, 0))
    edge[too].append((frm, 0))

class BFS:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = deque()

    def calc(self, start):
        self.dist[start] = 0
        self.q.append((0, start))
        while len(self.q) != 0:
            prov_cost, src = self.q.popleft()
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    if cost == 1:
                        self.q.append((self.dist[dest], dest))
                    else:
                        self.q.appendleft((self.dist[dest], dest))
        return self.dist

bfs = BFS(edge)
bfs.calc(comp[(0, 0)])
ans = bfs.dist[comp[(n-1, 0)]]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from heapq import heappop, heappush
INF = 10**9

n, m = map(int, input().split())
pqc = []

seen = set()
for i in range(n):
    seen.add((i, 0))
for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1
    pqc.append((p, q, c))
    seen.add((p, c))
    seen.add((q, c))
comp = dict()
for i, node in enumerate(seen):
    comp[node] = i

edge = [[] for _ in range(len(comp))]
for key in comp.keys():
    v, c = key
    if c != 0:
        frm = comp[(v, c)]
        too = comp[(v, 0)]
        edge[frm].append((too, 0))
        edge[too].append((frm, 1))

for p, q, c in pqc:
    frm = comp[(p, c)]
    too = comp[(q, c)]
    edge[frm].append((too, 0))
    edge[too].append((frm, 0))

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heappush(self.q, (self.dist[dest], dest))
        return self.dist

DIJK = Dijkstra(edge)
DIJK.calc(comp[(0, 0)])
ans = DIJK.dist[comp[(n-1, 0)]]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**9

n, m = map(int, input().split())
pqc = []

seen = set()
for i in range(n):
    seen.add((i, 0))
for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1
    pqc.append((p, q, c))
    seen.add((p, c))
    seen.add((q, c))
comp = dict()
for i, node in enumerate(seen):
    comp[node] = i

edge = [[] for _ in range(len(comp))]
for key in comp.keys():
    v, c = key
    if c != 0:
        frm = comp[(v, c)]
        too = comp[(v, 0)]
        edge[frm].append((too, 0))
        edge[too].append((frm, 1))

for p, q, c in pqc:
    frm = comp[(p, c)]
    too = comp[(q, c)]
    edge[frm].append((too, 0))
    edge[too].append((frm, 0))

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

DIJK = Dijkstra(edge)
DIJK.calc(comp[(0, 0)])
ans = DIJK.dist[comp[(n-1, 0)]]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**9

n, m = map(int, input().split())
pqc = []
edge = dict()
for i in range(n):
    edge[(i, 0)] = []

for _ in range(m):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1
    if (p, c) not in edge.keys():
        edge[(p, c)] = []
    if (q, c) not in edge.keys():
        edge[(q, c)] = []
    edge[(p, c)].append((q, c, 0))
    edge[(q, c)].append((p, c, 0))
    edge[(p, c)].append((p, 0, 0))
    edge[(p, 0)].append((p, c, 1))
    edge[(q, c)].append((q, 0, 0))
    edge[(q, 0)].append((q, c, 1))

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = dict() 
        for key in adj.keys():
            for p, c, d in adj[key]:
                self.dist[(p, c)] = INF
        for i in range(n):
            self.dist[(i, 0)] = INF
        self.dist[(0, 0)] = 0
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for nv, c, cost in self.adj[src]:
                dest = (nv, c)
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

DIJK = Dijkstra(edge)
DIJK.calc((0, 0))
if DIJK.dist[(n-1, 0)] == INF:
    print(-1)
else:
    print(DIJK.dist[(n-1, 0)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    costs = [10 ** 9] * n
    corporations = [set() for _ in range(n)]
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if costs[v] < d or e in corporations[v]:
            continue
        costs[v] = d
        corporations[v].add(e)
        for u, c in links[v]:
            if c == e:
                nd = d
                func = q.appendleft
            else:
                nd = d + 1
                func = q.append
            if costs[u] < nd or c in corporations[u]:
                continue
            costs[u] = nd
            func((nd, u, c))
    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [set() for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p].add((q, c))
    links[q].add((p, c))

print(bfs01(0, n - 1, links))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    costs = [10 ** 9] * n
    corporations = [set() for _ in range(n)]
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if costs[v] < d or e in corporations[v]:
            continue
        costs[v] = d
        corporations[v].add(e)
        for u, c in links[v]:
            if c == e:
                nd = d
                func = q.appendleft
            else:
                nd = d + 1
                func = q.append
            if costs[u] < nd or c in corporations[u]:
                continue
            func((nd, u, c))
    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [set() for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p].add((q, c))
    links[q].add((p, c))

print(bfs01(0, n - 1, links))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    costs = [10 ** 9] * n
    corporations = [set() for _ in range(n)]
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if costs[v] < d:
            continue
        elif costs[v] == d:
            if e in corporations[v]:
                continue
        else:
            costs[v] = d
        corporations[v].add(e)
        for u, c in links[v]:
            if c == e:
                nd = d
                func = q.appendleft
            else:
                nd = d + 1
                func = q.append
            if costs[u] < nd or c in corporations[u]:
                continue
            func((nd, u, c))
    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [set() for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p].add((q, c))
    links[q].add((p, c))

print(bfs01(0, n - 1, links))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        for u, c in links[v]:
            if u in visited:
                continue
            if c == e:
                q.appendleft((d, u, c))
            else:
                q.append((d + 1, u, c))
    return -1


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin:
    p, q, c = map(int, line.split())
    p -= 1
    q -= 1
    links[p].add((q, c))
    links[q].add((p, c))

print(bfs01(0, n - 1, links))

Submission status: Time Limit Exceeded

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


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))

    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    flag = [1] * (N+1)
    while deq:
        v = deq.pop()
        flag[v] = 1
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    if flag[u]:
                        deq.append(u)
                        flag[u] = 0
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    flag[u] = 0
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    flag[u] = 0
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)

    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))

    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    flag = [1] * (N+1)
    while deq:
        v = deq.pop()
        flag[v] = 1
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    if flag[u]:
                        deq.append(u)
                        flag[u] = 0
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)

    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))
    
    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    while deq:
        v = deq.pop()
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    deq.append(u)
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)
    
    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, q, c = map(int, input().split())
    adj[p].append((q, c))
    adj[q].append((p, c))

deq = deque()
cost = [10 ** 7] * (N+1)
seen = [defaultdict(int) for _ in range(N+1)]
prev = defaultdict(list)
deq.append(1)
cost[1] = 0
while deq:
    v = deq.pop()
    for uc in adj[v]:
        u, c = uc
        # print(v, u, c)
        # print(deq, prev, cost)
        # print(seen[4])
        if c in prev[v] and seen[u][c] == 0:
            if cost[u] == cost[v]:
                prev[u].append(c)
                deq.append(u)
            elif cost[u] > cost[v]:
                cost[u] = cost[v]
                deq.append(u)
                prev[u] = [c]
            seen[v][c] = 1
        else:
            if cost[u] > cost[v] + 1:
                cost[u] = cost[v] + 1
                deq.appendleft(u)
                prev[u] = [c]
            elif cost[u] == cost[v] + 1:
                prev[u].append(c)

print(cost[N]) if cost[N] < 10 ** 7 else print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

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

chg = 10**6
G = defaultdict(set)
for _ in range(M):
    p, q, c = map(int, input().split())
    # 無向グラフ
    G[p].add(p+chg*c)
    G[p+chg*c].add(p)
    G[q].add(q+chg*c)
    G[q+chg*c].add(q)
    G[p+chg*c].add(q+chg*c)
    G[q+chg*c].add(p+chg*c)


dist = defaultdict(lambda: 10**11)
dist[1] = 0

que = deque([1])

while que:
    ci = que.popleft()

    for ni in G[ci]:
        if dist[ni] == 10**11:
            if ci >= chg and ni >= chg:
                dist[ni] = dist[ci]
                que.appendleft(ni)
            else:
                dist[ni] = dist[ci]+1
                que.append(ni)


if dist[N] < 10**11:
    print(dist[N]//2)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque

N,M = map(int,input().split())
PQC = [tuple(map(int,input().split())) for i in range(M)]

ctoe = defaultdict(lambda: defaultdict(lambda: []))
vtoc = [set() for i in range(N)]

for p,q,c in PQC:
    p,q = p-1,q-1
    ctoe[c][p].append(q)
    ctoe[c][q].append(p)
    vtoc[p].add(c)
    vtoc[q].add(c)

INF = float('inf')
costs = [defaultdict(lambda: INF) for i in range(N)]
costs[0][0] = 0
q = deque([(0,0)])
while q:
    v,c = q.popleft()
    d = costs[v][c]
    if v==N-1:
        print(d)
        exit()
    for to in ctoe[c][v]:
        if d >= costs[to][c]: continue
        costs[to][c] = d
        q.appendleft((to,c))
    for c2 in vtoc[v]:
        if c==c2: continue
        for to in ctoe[c2][v]:
            if d+1 >= costs[to][c2]: continue
            costs[to][c2] = d+1
            q.append((to,c2))
print(-1)