結果
問題 |
No.2915 辺更新価値最大化
|
ユーザー |
![]() |
提出日時 | 2024-10-31 02:16:15 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 850 bytes |
コンパイル時間 | 509 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 85,456 KB |
最終ジャッジ日時 | 2024-10-31 02:16:24 |
合計ジャッジ時間 | 8,554 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 24 |
ソースコード
import sys input = sys.stdin.readline from heapq import heappop,heappush N,M,C=map(int,input().split()) EDGE=[list(map(int,input().split())) for i in range(M)] for i in range(M): EDGE[i][0]-=1 EDGE[i][1]-=1 Q=list(map(int,input().split())) for i in range(C): Q[i]-=1 USE=[1]*M for q in Q: USE[q]^=1 DP=[-1<<63]*N DP[0]=0 Q=[(0,0)] E=[[] for i in range(N)] for i in range(M): if USE[i]==0: continue x,y,dis=EDGE[i] E[x].append((y,dis)) #print(E) while Q: now,ind=heappop(Q) if DP[ind]!=now: continue now=-now for to,w in E[ind]: if DP[to]<now+w: DP[to]=now+w heappush(Q,(DP[to],to)) if DP[-1]<-1000000000: print("NaN") else: print(DP[-1])