結果
問題 |
No.2915 辺更新価値最大化
|
ユーザー |
![]() |
提出日時 | 2024-11-01 06:54:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,904 bytes |
コンパイル時間 | 517 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 77,780 KB |
最終ジャッジ日時 | 2024-11-01 06:54:52 |
合計ジャッジ時間 | 5,388 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 WA * 14 |
ソースコード
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 USE=[0]*N E=[[] for i in range(N)] for i in range(M): u,v,w=EDGE[i] E[u].append((v,i)) Q=[0] NO=[] while Q: x=Q.pop() USE[x]=1 for to,ind in E[x]: if USE[to]==1: NO.append(ind) else: USE[to]=1 Q.append(to) E=[[] for i in range(N)] E_INV=[[] for i in range(N)] NO=set(NO) for i in range(M): if i in NO: continue 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])