結果
問題 | No.1545 [Cherry 2nd Tune N] Anthem |
ユーザー |
![]() |
提出日時 | 2021-06-11 23:37:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 512 ms / 3,000 ms |
コード長 | 2,013 bytes |
コンパイル時間 | 573 ms |
コンパイル使用メモリ | 82,500 KB |
実行使用メモリ | 117,656 KB |
最終ジャッジ日時 | 2024-12-15 03:15:37 |
合計ジャッジ時間 | 15,496 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 67 |
ソースコード
import sys input = sys.stdin.readline import heapq N,S,T,K=map(int,input().split()) X=[0]+list(map(int,input().split())) M=int(input()) E=[[] for i in range(N+1)] for i in range(M): a,b,y=map(int,input().split()) E[a].append((b,y)) DP=[1<<60]*(N+1) FR=[-1]*(N+1) DP[S]=X[S] Q=[(X[S],S)] while Q: time,ind=heapq.heappop(Q) if time>DP[ind]: continue for to,cost in E[ind]: if DP[to]>DP[ind]+X[to]+cost: DP[to]=DP[ind]+X[to]+cost FR[to]=ind heapq.heappush(Q,(DP[to],to)) if DP[T]==1<<60: print("Impossible") exit() ANS=[] now=T while now!=-1: ANS.append(now) now=FR[now] if len(ANS)>=K: print("Possible") print(DP[T]) print(len(ANS)) print(*ANS[::-1]) exit() DP=[[1<<60]*(N+1) for i in range(K)] FR=[[-1]*(N+1) for i in range(K)] DP[0][S]=X[S] for i in range(K-1): for j in range(1,N+1): if DP[i][j]==1<<60: continue for to,cost in E[j]: if DP[i+1][to]>DP[i][j]+cost+X[to]: DP[i+1][to]=DP[i][j]+cost+X[to] FR[i+1][to]=j ANSX=DP[K-1][T] DP=DP[K-1] FR2=[-1]*(N+1) Q=[] for i in range(N+1): Q.append((DP[i],i)) heapq.heapify(Q) while Q: time,ind=heapq.heappop(Q) if time>DP[ind]: continue for to,cost in E[ind]: if DP[to]>DP[ind]+X[to]+cost: DP[to]=DP[ind]+X[to]+cost FR2[to]=ind heapq.heappush(Q,(DP[to],to)) if DP[T]==1<<60: print("Impossible") exit() elif ANSX<=DP[T]: print("Possible") print(ANSX) ANS=[T] for j in range(K-1,0,-1): ANS.append(FR[j][ANS[-1]]) print(len(ANS)) print(*ANS[::-1]) else: print("Possible") print(DP[T]) ANS=[T] now=T while now!=-1 and DP[FR2[now]]<DP[now]: now=FR2[now] ANS.append(now) for j in range(K-1,0,-1): ANS.append(FR[j][ANS[-1]]) print(len(ANS)) print(*ANS[::-1])