Submission #4631462


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(10**5*c + q)
    Edge[q].append(10**5*c + p)
    comp.add(c)
dist = {1: 0}
Q = deque()
Q.append(1)
visited = set()
while Q:
    cp, vn = divmod(Q.pop(), 10**5)
    if cp*10**5 + vn in visited:
        continue
    visited.add(cp*10**5 + vn)
    for j in Edge[vn]:
        cf, vf = divmod(j, 10**5)
        if cp*10**5 + vf in visited:
            continue
        if cp == cf:
            dist[cf*10**5 + vf] = min(dist.get(cf*10**5 + vf, 10**9), dist.get(cp*10**5 + vn, 10**9))
            Q.append(cf*10**5 + vf)
        else:
            dist[cf*10**5 + vf] = min(dist.get(cf*10**5 + vf, 10**9), 1 + dist.get(cp*10**5 + vn, 10**9))
            Q.appendleft(cf*10**5 + vf)
L = [dist.get(c*10**5 + N, 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 1033 Byte
Status WA
Exec Time 3183 ms
Memory 453084 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
AC × 36
WA × 10
TLE × 13
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 AC 183 ms 40176 KB
02.txt TLE 3173 ms 289156 KB
03.txt AC 1626 ms 161476 KB
04.txt AC 465 ms 55472 KB
05.txt AC 1066 ms 127904 KB
06.txt AC 483 ms 97712 KB
07.txt WA 528 ms 100528 KB
08.txt AC 1509 ms 143804 KB
09.txt AC 599 ms 104112 KB
10.txt AC 625 ms 104368 KB
11.txt AC 836 ms 111872 KB
12.txt AC 494 ms 72796 KB
13.txt AC 720 ms 95964 KB
14.txt AC 752 ms 100400 KB
15.txt AC 580 ms 77104 KB
16.txt AC 703 ms 93984 KB
17.txt AC 952 ms 123824 KB
18.txt AC 562 ms 71004 KB
19.txt AC 678 ms 104496 KB
20.txt AC 1385 ms 128452 KB
21.txt TLE 3183 ms 453084 KB
22.txt TLE 3172 ms 283216 KB
23.txt AC 2127 ms 170320 KB
24.txt WA 876 ms 121648 KB
25.txt AC 603 ms 88796 KB
26.txt AC 682 ms 91612 KB
27.txt WA 897 ms 116140 KB
28.txt AC 818 ms 117040 KB
29.txt WA 880 ms 120096 KB
30.txt AC 765 ms 102704 KB
31.txt AC 1003 ms 123612 KB
32.txt AC 662 ms 100144 KB
33.txt WA 909 ms 118304 KB
34.txt TLE 3177 ms 360152 KB
35.txt AC 436 ms 67164 KB
36.txt AC 1263 ms 139996 KB
37.txt TLE 3178 ms 383444 KB
38.txt TLE 3177 ms 352984 KB
sample_01.txt AC 161 ms 38256 KB
sample_02.txt AC 161 ms 38256 KB
sample_03.txt AC 164 ms 38256 KB
w1.txt WA 830 ms 114992 KB
w10.txt AC 832 ms 114780 KB
w11.txt TLE 3179 ms 384136 KB
w12.txt TLE 3175 ms 315016 KB
w13.txt TLE 3163 ms 138760 KB
w14.txt AC 1522 ms 124636 KB
w15.txt AC 587 ms 87516 KB
w16.txt AC 603 ms 86748 KB
w17.txt AC 657 ms 86236 KB
w18.txt AC 712 ms 70748 KB
w2.txt WA 894 ms 116912 KB
w3.txt WA 941 ms 115012 KB
w4.txt WA 615 ms 84400 KB
w5.txt TLE 3174 ms 327808 KB
w6.txt WA 1695 ms 147540 KB
w7.txt TLE 3175 ms 322300 KB
w8.txt TLE 3170 ms 252668 KB
w9.txt TLE 3163 ms 138876 KB