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