Submission #76747237

Source Code Expand

n,m,k=map(int,input().split())
H=list(map(int,input().split()))
g=[[] for i in range(n)]
for i in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    g[u].append(v)
    g[v].append(u)
from collections import deque
que=deque()
que.append((0,1,H[0]))#位置、距離、高さ
import math
is_visited=[math.inf for i in range(n)]

while que:
    v,l,h=que.popleft()
    if is_visited[v]<h or l==k:
        continue
    for nv in g[v]:
        nh=max(h,H[nv])
        if is_visited[nv]<=nh:continue
        is_visited[nv]=nh
        que.append((nv,l+1,nh))
ans=is_visited[-1]
if ans==math.inf:
    print(-1)
else:
    print(ans)

Submission Info

Submission Time
Task D - Selection of a Mountain Climbing Route
User st0123
Language Python (PyPy 3.11-v7.3.20)
Score 400
Code Size 662 Byte
Status AC
Exec Time 1200 ms
Memory 213352 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 5
AC × 90
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt
All sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in48.txt, in49.txt, in50.txt, in51.txt, in52.txt, in53.txt, in54.txt, in55.txt, in56.txt, in57.txt, in58.txt, in59.txt, in60.txt, in61.txt, in62.txt, in63.txt, in64.txt, in65.txt, in66.txt, in67.txt, in68.txt, in69.txt, in70.txt, in71.txt, in72.txt, in73.txt, in74.txt, in75.txt, in76.txt, in77.txt, in78.txt, in79.txt, in80.txt, in81.txt, in82.txt, in83.txt, in84.txt, in85.txt
Case Name Status Exec Time Memory
in01.txt AC 64 ms 93516 KiB
in02.txt AC 63 ms 93524 KiB
in03.txt AC 63 ms 93480 KiB
in04.txt AC 63 ms 93616 KiB
in05.txt AC 230 ms 127860 KiB
in06.txt AC 332 ms 127720 KiB
in07.txt AC 86 ms 109184 KiB
in08.txt AC 221 ms 127832 KiB
in09.txt AC 63 ms 93480 KiB
in10.txt AC 592 ms 134732 KiB
in11.txt AC 452 ms 133196 KiB
in12.txt AC 460 ms 132896 KiB
in13.txt AC 305 ms 127796 KiB
in14.txt AC 418 ms 131112 KiB
in15.txt AC 441 ms 130720 KiB
in16.txt AC 440 ms 134256 KiB
in17.txt AC 64 ms 93628 KiB
in18.txt AC 187 ms 127904 KiB
in19.txt AC 433 ms 133000 KiB
in20.txt AC 312 ms 126576 KiB
in21.txt AC 404 ms 130508 KiB
in22.txt AC 338 ms 125856 KiB
in23.txt AC 436 ms 132944 KiB
in24.txt AC 343 ms 126580 KiB
in25.txt AC 336 ms 126852 KiB
in26.txt AC 404 ms 130132 KiB
in27.txt AC 420 ms 130348 KiB
in28.txt AC 324 ms 127832 KiB
in29.txt AC 63 ms 93480 KiB
in30.txt AC 63 ms 93676 KiB
in31.txt AC 63 ms 93584 KiB
in32.txt AC 63 ms 93744 KiB
in33.txt AC 63 ms 93516 KiB
in34.txt AC 63 ms 93604 KiB
in35.txt AC 63 ms 93748 KiB
in36.txt AC 62 ms 93408 KiB
in37.txt AC 62 ms 93872 KiB
in38.txt AC 63 ms 93976 KiB
in39.txt AC 62 ms 93480 KiB
in40.txt AC 174 ms 125504 KiB
in41.txt AC 362 ms 130228 KiB
in42.txt AC 85 ms 109680 KiB
in43.txt AC 180 ms 127600 KiB
in44.txt AC 64 ms 93344 KiB
in45.txt AC 63 ms 93756 KiB
in46.txt AC 249 ms 114124 KiB
in47.txt AC 246 ms 113904 KiB
in48.txt AC 315 ms 126516 KiB
in49.txt AC 313 ms 126576 KiB
in50.txt AC 438 ms 133064 KiB
in51.txt AC 453 ms 133560 KiB
in52.txt AC 443 ms 130800 KiB
in53.txt AC 437 ms 129804 KiB
in54.txt AC 577 ms 150836 KiB
in55.txt AC 1200 ms 213352 KiB
in56.txt AC 490 ms 133444 KiB
in57.txt AC 483 ms 133328 KiB
in58.txt AC 495 ms 133960 KiB
in59.txt AC 237 ms 127792 KiB
in60.txt AC 447 ms 133376 KiB
in61.txt AC 474 ms 133468 KiB
in62.txt AC 434 ms 130568 KiB
in63.txt AC 431 ms 130764 KiB
in64.txt AC 455 ms 133460 KiB
in65.txt AC 458 ms 133600 KiB
in66.txt AC 63 ms 93464 KiB
in67.txt AC 62 ms 93604 KiB
in68.txt AC 313 ms 127600 KiB
in69.txt AC 315 ms 127788 KiB
in70.txt AC 85 ms 127348 KiB
in71.txt AC 84 ms 127500 KiB
in72.txt AC 63 ms 93576 KiB
in73.txt AC 62 ms 93604 KiB
in74.txt AC 61 ms 93420 KiB
in75.txt AC 63 ms 93676 KiB
in76.txt AC 63 ms 93480 KiB
in77.txt AC 64 ms 93616 KiB
in78.txt AC 63 ms 93628 KiB
in79.txt AC 63 ms 93748 KiB
in80.txt AC 63 ms 93464 KiB
in81.txt AC 63 ms 93524 KiB
in82.txt AC 209 ms 125368 KiB
in83.txt AC 203 ms 125504 KiB
in84.txt AC 403 ms 130952 KiB
in85.txt AC 311 ms 126584 KiB
sample01.txt AC 63 ms 93436 KiB
sample02.txt AC 63 ms 93564 KiB
sample03.txt AC 63 ms 93616 KiB
sample04.txt AC 64 ms 93608 KiB
sample05.txt AC 63 ms 93748 KiB