Submission #4631162


Source Code Expand

import sys
from collections import deque
N, M = map(int, input().split())
Edge = [[] for _ in range(N+1)]
comp = set()
for _ in range(M):
    p, q, c = map(int, sys.stdin.readline().split())
    Edge[p].append((q, c))
    Edge[q].append((p, c))
    comp.add(c)
dist = {(1, 0): 0}
Q = deque()
Q.append((1, 0))
visited = set()
while Q:
    vn, cp = Q.pop()
    if (vn, cp) in visited:
        continue
    visited.add((vn, cp))
    for vf, cf in Edge[vn]:
        if (vf, cp) in visited:
        continue
        if cp == cf:
            dist[(vf, cf)] = min(dist.get((vf, cf), 10**9), dist.get((vn, cp), 10**9))
            Q.append((vf, cf))
        else:
            dist[(vf, cf)] = min(dist.get((vf, cf), 10**9), 1 + dist.get((vn, cp), 10**9))
            Q.appendleft((vf, cf))
L = [dist.get((N, c), 10**9) for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User Tallfall
Language PyPy3 (2.4.0)
Score 0
Code Size 924 Byte
Status RE
Exec Time 173 ms
Memory 38384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
RE × 59
Set Name Test Cases
Sample
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt
Case Name Status Exec Time Memory
01.txt RE 165 ms 38384 KB
02.txt RE 161 ms 38256 KB
03.txt RE 161 ms 38256 KB
04.txt RE 170 ms 38256 KB
05.txt RE 162 ms 38256 KB
06.txt RE 170 ms 38256 KB
07.txt RE 162 ms 38256 KB
08.txt RE 162 ms 38256 KB
09.txt RE 160 ms 38256 KB
10.txt RE 164 ms 38256 KB
11.txt RE 160 ms 38256 KB
12.txt RE 170 ms 38256 KB
13.txt RE 166 ms 38256 KB
14.txt RE 166 ms 38256 KB
15.txt RE 163 ms 38256 KB
16.txt RE 173 ms 38256 KB
17.txt RE 162 ms 38256 KB
18.txt RE 163 ms 38256 KB
19.txt RE 171 ms 38256 KB
20.txt RE 165 ms 38256 KB
21.txt RE 163 ms 38256 KB
22.txt RE 159 ms 38256 KB
23.txt RE 161 ms 38256 KB
24.txt RE 160 ms 38256 KB
25.txt RE 160 ms 38256 KB
26.txt RE 161 ms 38256 KB
27.txt RE 168 ms 38256 KB
28.txt RE 161 ms 38256 KB
29.txt RE 160 ms 38256 KB
30.txt RE 160 ms 38256 KB
31.txt RE 161 ms 38384 KB
32.txt RE 160 ms 38256 KB
33.txt RE 160 ms 38256 KB
34.txt RE 162 ms 38256 KB
35.txt RE 160 ms 38256 KB
36.txt RE 168 ms 38256 KB
37.txt RE 161 ms 38256 KB
38.txt RE 160 ms 38256 KB
sample_01.txt RE 161 ms 38256 KB
sample_02.txt RE 166 ms 38384 KB
sample_03.txt RE 171 ms 38256 KB
w1.txt RE 161 ms 38256 KB
w10.txt RE 164 ms 38256 KB
w11.txt RE 162 ms 38256 KB
w12.txt RE 162 ms 38256 KB
w13.txt RE 164 ms 38256 KB
w14.txt RE 160 ms 38256 KB
w15.txt RE 162 ms 38256 KB
w16.txt RE 164 ms 38256 KB
w17.txt RE 161 ms 38256 KB
w18.txt RE 162 ms 38256 KB
w2.txt RE 163 ms 38256 KB
w3.txt RE 165 ms 38256 KB
w4.txt RE 161 ms 38256 KB
w5.txt RE 161 ms 38256 KB
w6.txt RE 161 ms 38256 KB
w7.txt RE 160 ms 38256 KB
w8.txt RE 163 ms 38256 KB
w9.txt RE 161 ms 38256 KB