結果

問題 No.2100 [Cherry Alpha C] Two-way Steps
ユーザー flippergoflippergo
提出日時 2024-09-24 09:21:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 816 ms / 2,000 ms
コード長 1,472 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 129,140 KB
最終ジャッジ日時 2024-09-24 09:22:04
合計ジャッジ時間 23,608 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
54,432 KB
testcase_01 AC 40 ms
55,824 KB
testcase_02 AC 40 ms
55,200 KB
testcase_03 AC 40 ms
54,040 KB
testcase_04 AC 649 ms
116,064 KB
testcase_05 AC 449 ms
106,048 KB
testcase_06 AC 210 ms
86,312 KB
testcase_07 AC 228 ms
88,332 KB
testcase_08 AC 646 ms
123,764 KB
testcase_09 AC 479 ms
101,424 KB
testcase_10 AC 270 ms
88,756 KB
testcase_11 AC 520 ms
109,124 KB
testcase_12 AC 393 ms
96,292 KB
testcase_13 AC 418 ms
113,972 KB
testcase_14 AC 380 ms
91,896 KB
testcase_15 AC 434 ms
111,452 KB
testcase_16 AC 361 ms
92,732 KB
testcase_17 AC 316 ms
111,876 KB
testcase_18 AC 435 ms
113,572 KB
testcase_19 AC 758 ms
123,660 KB
testcase_20 AC 268 ms
89,864 KB
testcase_21 AC 371 ms
94,784 KB
testcase_22 AC 355 ms
92,436 KB
testcase_23 AC 610 ms
118,340 KB
testcase_24 AC 787 ms
128,868 KB
testcase_25 AC 816 ms
128,496 KB
testcase_26 AC 800 ms
128,600 KB
testcase_27 AC 777 ms
129,140 KB
testcase_28 AC 777 ms
128,108 KB
testcase_29 AC 774 ms
128,672 KB
testcase_30 AC 740 ms
128,728 KB
testcase_31 AC 682 ms
128,480 KB
testcase_32 AC 699 ms
128,372 KB
testcase_33 AC 694 ms
128,988 KB
testcase_34 AC 392 ms
95,440 KB
testcase_35 AC 327 ms
94,588 KB
testcase_36 AC 316 ms
94,736 KB
testcase_37 AC 298 ms
94,024 KB
testcase_38 AC 361 ms
95,780 KB
testcase_39 AC 235 ms
92,060 KB
testcase_40 AC 237 ms
92,588 KB
testcase_41 AC 239 ms
91,920 KB
testcase_42 AC 277 ms
92,832 KB
testcase_43 AC 249 ms
92,852 KB
testcase_44 AC 282 ms
124,480 KB
testcase_45 AC 277 ms
124,496 KB
testcase_46 AC 270 ms
127,628 KB
testcase_47 AC 278 ms
128,040 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
N,M = map(int,input().split())
H = [0]+list(map(int,input().split()))
G0 = {i:[] for i in range(1,N+1)}
Indeg0 = [0]*(N+1)
G1 = {i:[] for i in range(1,N+1)}
Indeg1 = [0]*(N+1)
for _ in range(M):
    a,b = map(int,input().split())
    if b>a:
        G0[a].append((b,max(H[b]-H[a],0)))
        Indeg0[b] += 1
        G1[b].append((a,max(H[a]-H[b],0)))
        Indeg1[a] += 1
    else:
        G0[b].append((a,max(H[a]-H[b],0)))
        Indeg0[a] += 1
        G1[a].append((b,max(H[b]-H[a],0)))
        Indeg1[b] += 1
INFTY = 10**15
dist0 = [[-INFTY,-INFTY] for _ in range(N+1)]
que0 = deque([1])
dist0[1] = [0,0]
for i in range(2,N+1):
    if Indeg0[i]==0:
        que0.append(i)
while que0:
    u = que0.popleft()
    d0,d1 = dist0[u]
    for v,d in G0[u]:
        if d>0:
            dist0[v][1] = max(dist0[v][1],d0+d)
        else:
            dist0[v][0] = max(dist0[v][0],d0,d1)
        Indeg0[v] -= 1
        if Indeg0[v]==0:
            que0.append(v)
dist1 = [[-INFTY,-INFTY] for _ in range(N+1)]
que1 = deque([N])
dist1[N] = [0,0]
for i in range(1,N):
    if Indeg1[i]==0:
        que1.append(i)
while que1:
    u = que1.popleft()
    d0,d1 = dist1[u]
    for v,d in G1[u]:
        if d>0:
            dist1[v][1] = max(dist1[v][1],d0+d)
        else:
            dist1[v][0] = max(dist1[v][0],d0,d1)
        Indeg1[v] -= 1
        if Indeg1[v]==0:
            que1.append(v)
print(max(max(dist0[N]),-1))
print(max(max(dist1[1]),-1))
0