結果
| 問題 | No.1545 [Cherry 2nd Tune N] Anthem |
| ユーザー |
 ygd.
|
| 提出日時 | 2021-06-15 22:59:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,037 bytes |
| コンパイル時間 | 232 ms |
| コンパイル使用メモリ | 82,248 KB |
| 実行使用メモリ | 199,804 KB |
| 最終ジャッジ日時 | 2024-06-08 15:26:50 |
| 合計ジャッジ時間 | 7,991 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 40 ms
58,752 KB |
| testcase_01 | AC | 40 ms
53,248 KB |
| testcase_02 | AC | 39 ms
53,076 KB |
| testcase_03 | AC | 43 ms
54,528 KB |
| testcase_04 | AC | 178 ms
95,468 KB |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| 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 | -- | - |
ソースコード
from heapq import heapify, heappop, heappush
from math import inf
def main():
N,S,T,K = map(int,input().split()); INF = float("inf")
S-=1;T-=1 #0-index
X = list(map(int,input().split()))
G = [[] for _ in range(N)]
M = int(input())
for _ in range(M):
A,B,Y = map(int,input().split())
A-=1;B-=1
G[A].append((Y,B))
def dijkstra_heap2(s,G,K):
INF = float("inf")
#S:start, V: node, E: Edge, G: Graph
V = len(G)
#dp[i][j]: i番目の歌を歌って今j曲目(i番目の歌を含む)
if K <= 10:
MAX = 20
elif K <= 130:
MAX = 1000
else:
MAX = pow(10,5)
dp = [[INF]*MAX for _ in range(V)]
#d = [INF for _ in range(V)]
dp[s][1] = X[s]
prev = [[-1]*MAX for _ in range(V)]
PQ = []
heappush(PQ,(X[s],s,1)) #時間, 位置, 何曲目
while PQ:
c,v,n = heappop(PQ)
if dp[v][n] < c:
continue
dp[v][n] = c
if n+1 >= MAX: #これ以上は配列外参照
continue
for cost,u in G[v]:
if dp[u][n+1] <= cost + X[u] + dp[v][n]:
continue
dp[u][n+1] = cost + X[u] + dp[v][n]
prev[u][n+1] = v
heappush(PQ,(dp[u][n+1], u, n+1))
return dp, prev
d, keiro = dijkstra_heap2(S,G,K)
#print(d)
#print(keiro)
ans = INF
num = INF #何曲か
for i in range(K,len(d[T])):
if d[T][i] < ans:
ans = d[T][i]
num = i
if ans == INF:
print("Impossible")
else:
print("Possible")
print(ans)
print(num)
ret = [T+1] #1-index
#num -= 1
now = T
while num > 1:
pre = keiro[now][num]
ret.append(pre+1) #1-index
now = pre
num -= 1
ret.reverse()
print(*ret)
if __name__ == '__main__':
main()