Submission #76910403

Source Code Expand

N, M, L, S, T = map(int, input().split())
graph = [[] for n in range(N + 1)]

for m in range(M):
    U, V, C = map(int, input().split())
    graph[U].append((V, C))

used = [[False] * (L + 1) for n in range(N + 1)]
used[1][0] = True

from collections import deque

queue = deque()

queue.append((1, 0, 0))
res = [False] * (N + 1)

while queue:
    q = queue.popleft()
    now = q[0]
    l = q[1]
    c = q[2]

    if l == L:
        if S <= c <= T:
            res[now] = True
        continue

    for neibor in graph[now]:
        nex = neibor[0]

        #if used[nex][l + 1]:
        #    continue

        if c + neibor[1] > T:
            continue

        used[nex][l + 1] = True
        queue.append((nex, l + 1, c + neibor[1]))

ret = []

for n in range(N + 1):
    if res[n]:
        ret.append(n)

print(*ret)

Submission Info

Submission Time
Task G - Paid Walk
User kurome_rome
Language Python (PyPy 3.11-v7.3.20)
Score 400
Code Size 866 Byte
Status AC
Exec Time 977 ms
Memory 292768 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 57
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, hand_14.txt, hand_15.txt, hand_16.txt, hand_17.txt, hand_18.txt, hand_19.txt, hand_20.txt, hand_21.txt, hand_22.txt, hand_23.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt
Case Name Status Exec Time Memory
example_00.txt AC 76 ms 93492 KiB
example_01.txt AC 76 ms 93672 KiB
example_02.txt AC 76 ms 93460 KiB
hand_00.txt AC 585 ms 160260 KiB
hand_01.txt AC 894 ms 200068 KiB
hand_02.txt AC 634 ms 177500 KiB
hand_03.txt AC 677 ms 185536 KiB
hand_04.txt AC 609 ms 167676 KiB
hand_05.txt AC 447 ms 160916 KiB
hand_06.txt AC 241 ms 205540 KiB
hand_07.txt AC 110 ms 112164 KiB
hand_08.txt AC 593 ms 230284 KiB
hand_09.txt AC 588 ms 230992 KiB
hand_10.txt AC 111 ms 135200 KiB
hand_11.txt AC 111 ms 134884 KiB
hand_12.txt AC 450 ms 160880 KiB
hand_13.txt AC 462 ms 160800 KiB
hand_14.txt AC 447 ms 156172 KiB
hand_15.txt AC 610 ms 168344 KiB
hand_16.txt AC 571 ms 162528 KiB
hand_17.txt AC 633 ms 283616 KiB
hand_18.txt AC 652 ms 285796 KiB
hand_19.txt AC 471 ms 153820 KiB
hand_20.txt AC 647 ms 285296 KiB
hand_21.txt AC 733 ms 286900 KiB
hand_22.txt AC 719 ms 177916 KiB
hand_23.txt AC 911 ms 199696 KiB
random_00.txt AC 491 ms 152032 KiB
random_01.txt AC 490 ms 151564 KiB
random_02.txt AC 493 ms 151736 KiB
random_03.txt AC 480 ms 152008 KiB
random_04.txt AC 476 ms 151720 KiB
random_05.txt AC 486 ms 151516 KiB
random_06.txt AC 489 ms 151864 KiB
random_07.txt AC 513 ms 152184 KiB
random_08.txt AC 486 ms 151740 KiB
random_09.txt AC 485 ms 150912 KiB
random_10.txt AC 463 ms 151536 KiB
random_11.txt AC 504 ms 152508 KiB
random_12.txt AC 481 ms 152620 KiB
random_13.txt AC 735 ms 232748 KiB
random_14.txt AC 634 ms 180696 KiB
random_15.txt AC 743 ms 233220 KiB
random_16.txt AC 461 ms 151708 KiB
random_17.txt AC 977 ms 292768 KiB
random_18.txt AC 512 ms 151472 KiB
random_19.txt AC 698 ms 284224 KiB
random_20.txt AC 508 ms 151828 KiB
random_21.txt AC 483 ms 150252 KiB
random_22.txt AC 487 ms 151552 KiB
random_23.txt AC 648 ms 229748 KiB
random_24.txt AC 487 ms 151568 KiB
random_25.txt AC 488 ms 151824 KiB
random_26.txt AC 472 ms 151612 KiB
random_27.txt AC 473 ms 151744 KiB
random_28.txt AC 495 ms 151612 KiB
random_29.txt AC 469 ms 151680 KiB