結果
問題 |
No.2915 辺更新価値最大化
|
ユーザー |
![]() |
提出日時 | 2024-11-01 07:02:00 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,539 bytes |
コンパイル時間 | 449 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 77,876 KB |
最終ジャッジ日時 | 2024-11-01 07:02:05 |
合計ジャッジ時間 | 4,636 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 WA * 4 |
ソースコード
import sys input = sys.stdin.readline 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 E=[[] for i in range(N)] E_INV=[[] for i in range(N)] for i in range(M): u,v,w=EDGE[i] E[u].append(v) E_INV[v].append(u) def Top_sort(E): Parent=[-1]*N USEIND=[0]*N TOP=[] for ROOT in range(1): if Parent[ROOT]!=-1: continue Parent[ROOT]=ROOT NOW=ROOT while NOW!=ROOT or USEIND[ROOT]!=len(E[ROOT]): if USEIND[NOW]==len(E[NOW]): TOP.append(NOW) NOW=Parent[NOW] elif E[NOW][USEIND[NOW]]==Parent[NOW]: USEIND[NOW]+=1 else: NEXT=E[NOW][USEIND[NOW]] USEIND[NOW]+=1 if Parent[NEXT]==-1: Parent[NEXT]=NOW NOW=NEXT TOP.append(ROOT) return TOP[::-1] TOP=Top_sort(E) 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 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)) for ind in TOP: for to,w in E[ind]: if DP[to]<DP[ind]+w: DP[to]=DP[ind]+w if DP[-1]<-1000000000: print("NaN") else: print(DP[-1])