結果
問題 | No.2100 [Cherry Alpha C] Two-way Steps |
ユーザー |
![]() |
提出日時 | 2022-10-14 22:32:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 531 ms / 2,000 ms |
コード長 | 1,116 bytes |
コンパイル時間 | 252 ms |
コンパイル使用メモリ | 82,556 KB |
実行使用メモリ | 132,892 KB |
最終ジャッジ日時 | 2024-06-26 15:53:35 |
合計ジャッジ時間 | 15,966 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
import sys input = sys.stdin.readline from collections import deque N,M=map(int,input().split()) H=list(map(int,input().split())) XY=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)] edge1 = [[] for _ in range(N)] edge2 = [[] for _ in range(N)] ins1 = [0]*N ins2 = [0]*N for x,y in XY: edge1[x].append((y,max(0, H[y]-H[x]))) ins1[y]+=1 edge2[y].append((x,max(0, H[x]-H[y]))) ins2[x]+=1 INF=10**60 def solve(edge, ins, start, goal): dp = [-INF]*N dp2 = [-INF]*N dp[start]=0 que = deque() for i,j in enumerate(ins): if j==0: que.append(i) while que: cur = que.popleft() u = dp[cur] u2 = dp2[cur] for to,h in edge[cur]: if h>0: dp2[to] = max(dp2[to], u + h) else: dp[to] = max(dp[to], u2, u) ins[to]-=1 if ins[to]==0: que.append(to) ans = max(dp[goal], dp2[goal]) if ans<0: print(-1) else: print(ans) # print(dp) # print(dp2) solve(edge1,ins1, 0, -1) solve(edge2,ins2, -1, 0)