結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
ユーザー titiatitia
提出日時 2021-06-11 23:26:01
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
MLE  
実行時間 -
コード長 1,521 bytes
コンパイル時間 95 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 817,784 KB
最終ジャッジ日時 2024-05-08 19:47:21
合計ジャッジ時間 7,592 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 236 ms
31,488 KB
testcase_01 AC 245 ms
34,432 KB
testcase_02 AC 32 ms
10,880 KB
testcase_03 AC 225 ms
28,160 KB
testcase_04 AC 232 ms
27,008 KB
testcase_05 AC 926 ms
48,104 KB
testcase_06 AC 405 ms
28,156 KB
testcase_07 AC 393 ms
33,244 KB
testcase_08 MLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
testcase_60 -- -
testcase_61 -- -
testcase_62 -- -
testcase_63 -- -
testcase_64 -- -
testcase_65 -- -
testcase_66 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

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(10**5+1)]
FR=[[-1]*(N+1) for i in range(10**5+1)]

DP[0][S]=X[S]

ANSX=1<<60
Q=[S]
ANSC=-1

for i in range(10**5):
    NQ=[]
    while Q:
        x=Q.pop()
        for to,cost in E[x]:
            if DP[i+1][to]>DP[i][x]+cost+X[to] and DP[i][x]+cost+X[to]<ANSX:
                DP[i+1][to]=DP[i][x]+cost+X[to]
                FR[i+1][to]=x
                NQ.append(to)
                
    Q=list(set(NQ))

    if ANSX>DP[i][T] and i>=K-1:
        ANSX=DP[i][T]
        ANSC=i

if ANSC==-1:
    print("Impossible")
else:
    print("Possible")
    print(ANSX)
    ANS=[T]
    for j in range(ANSC,0,-1):
        ANS.append(FR[j][ANS[-1]])
    print(len(ANS))
    print(*ANS[::-1])
    

            
            
0