Submission #36759317

Source Code Expand

from collections import deque, defaultdict

def E(N, M, K, uva, s):
    edge = defaultdict(list)
    
    for u, v, a in uva:
        if not a:
            u = -u
            v = -v
        edge[u].append(v)
        edge[v].append(u)
    
    for s in s:
        edge[s].append(-s)
        edge[-s].append(s)
    
    q = deque([1])
    passed = set([1])
    route = {}
    while q:
        now = q.popleft()
        for e in edge[now]:
            if e in passed:
                continue
            
            route[e] = now
            if e == N or -e == N:
                break
            if now == -e:
                q.appendleft(e)
            else:
                q.append(e)
            passed.add(e)
        else:
            continue
        break
    else:
        return -1
    
    ans = 0
    now = e
    while now != 1:
        nxt = route[now]
        if now != -nxt:
            ans += 1
        now = nxt
    
    return ans

N, M, K = map(int, input().split())
uva = [list(map(int, input().split())) for _ in range(M)]
*s, = map(int, input().split())
print(E(N, M, K, uva, s))

Submission Info

Submission Time
Task E - Crystal Switches
User arakaki_tokyo
Language PyPy3 (7.3.0)
Score 500
Code Size 1154 Byte
Status AC
Exec Time 887 ms
Memory 284576 KiB

Judge Result

Set Name Sample All AfterContest
Score / Max Score 0 / 0 500 / 500 0 / 0
Status
AC × 2
AC × 63
AC × 1
Set Name Test Cases
Sample example0.txt, example1.txt
All example0.txt, example1.txt, 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt
AfterContest after_contest_01.txt
Case Name Status Exec Time Memory
000.txt AC 349 ms 130320 KiB
001.txt AC 327 ms 130704 KiB
002.txt AC 332 ms 130800 KiB
003.txt AC 331 ms 130808 KiB
004.txt AC 346 ms 128264 KiB
005.txt AC 548 ms 191144 KiB
006.txt AC 768 ms 277576 KiB
007.txt AC 773 ms 284576 KiB
008.txt AC 642 ms 223296 KiB
009.txt AC 553 ms 178492 KiB
010.txt AC 568 ms 180888 KiB
011.txt AC 541 ms 190244 KiB
012.txt AC 400 ms 153504 KiB
013.txt AC 420 ms 160052 KiB
014.txt AC 338 ms 111656 KiB
015.txt AC 593 ms 182712 KiB
016.txt AC 887 ms 257060 KiB
017.txt AC 745 ms 223244 KiB
018.txt AC 635 ms 199620 KiB
019.txt AC 624 ms 200224 KiB
020.txt AC 654 ms 208912 KiB
021.txt AC 366 ms 126080 KiB
022.txt AC 339 ms 129776 KiB
023.txt AC 179 ms 138168 KiB
024.txt AC 245 ms 110832 KiB
025.txt AC 417 ms 127216 KiB
026.txt AC 427 ms 123292 KiB
027.txt AC 408 ms 121392 KiB
028.txt AC 384 ms 114064 KiB
029.txt AC 390 ms 115068 KiB
030.txt AC 421 ms 124664 KiB
031.txt AC 370 ms 111336 KiB
032.txt AC 397 ms 118556 KiB
033.txt AC 390 ms 114696 KiB
034.txt AC 379 ms 112888 KiB
035.txt AC 372 ms 111256 KiB
036.txt AC 379 ms 112712 KiB
037.txt AC 377 ms 113404 KiB
038.txt AC 380 ms 112224 KiB
039.txt AC 382 ms 112168 KiB
040.txt AC 341 ms 111440 KiB
041.txt AC 368 ms 111168 KiB
042.txt AC 364 ms 111816 KiB
043.txt AC 350 ms 111552 KiB
044.txt AC 357 ms 111944 KiB
045.txt AC 361 ms 111692 KiB
046.txt AC 341 ms 111168 KiB
047.txt AC 363 ms 111584 KiB
048.txt AC 339 ms 111272 KiB
049.txt AC 345 ms 111388 KiB
050.txt AC 365 ms 111648 KiB
051.txt AC 382 ms 115872 KiB
052.txt AC 375 ms 114940 KiB
053.txt AC 370 ms 114468 KiB
054.txt AC 381 ms 116016 KiB
055.txt AC 363 ms 112140 KiB
056.txt AC 384 ms 112272 KiB
057.txt AC 394 ms 117736 KiB
058.txt AC 395 ms 117920 KiB
059.txt AC 385 ms 116620 KiB
060.txt AC 382 ms 111740 KiB
after_contest_01.txt AC 523 ms 213172 KiB
example0.txt AC 54 ms 65280 KiB
example1.txt AC 52 ms 64904 KiB