結果
問題 | No.1545 [Cherry 2nd Tune N] Anthem |
ユーザー | taiga0629kyopro |
提出日時 | 2021-06-11 22:07:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,993 ms / 3,000 ms |
コード長 | 1,543 bytes |
コンパイル時間 | 301 ms |
コンパイル使用メモリ | 86,832 KB |
実行使用メモリ | 374,304 KB |
最終ジャッジ日時 | 2023-08-21 12:36:46 |
合計ジャッジ時間 | 41,133 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,264 KB |
testcase_01 | AC | 75 ms
71,044 KB |
testcase_02 | AC | 79 ms
71,112 KB |
testcase_03 | AC | 75 ms
71,408 KB |
testcase_04 | AC | 469 ms
172,628 KB |
testcase_05 | AC | 1,993 ms
327,708 KB |
testcase_06 | AC | 609 ms
168,092 KB |
testcase_07 | AC | 543 ms
158,504 KB |
testcase_08 | AC | 1,445 ms
257,532 KB |
testcase_09 | AC | 537 ms
128,140 KB |
testcase_10 | AC | 285 ms
114,504 KB |
testcase_11 | AC | 799 ms
205,552 KB |
testcase_12 | AC | 1,398 ms
286,664 KB |
testcase_13 | AC | 412 ms
130,748 KB |
testcase_14 | AC | 526 ms
186,576 KB |
testcase_15 | AC | 213 ms
90,556 KB |
testcase_16 | AC | 674 ms
230,328 KB |
testcase_17 | AC | 254 ms
88,112 KB |
testcase_18 | AC | 643 ms
133,456 KB |
testcase_19 | AC | 698 ms
168,112 KB |
testcase_20 | AC | 494 ms
133,048 KB |
testcase_21 | AC | 788 ms
259,456 KB |
testcase_22 | AC | 497 ms
170,244 KB |
testcase_23 | AC | 613 ms
121,788 KB |
testcase_24 | AC | 181 ms
88,008 KB |
testcase_25 | AC | 209 ms
95,852 KB |
testcase_26 | AC | 99 ms
76,436 KB |
testcase_27 | AC | 175 ms
84,884 KB |
testcase_28 | AC | 236 ms
105,148 KB |
testcase_29 | AC | 214 ms
97,364 KB |
testcase_30 | AC | 192 ms
93,756 KB |
testcase_31 | AC | 229 ms
94,464 KB |
testcase_32 | AC | 200 ms
85,324 KB |
testcase_33 | AC | 239 ms
102,144 KB |
testcase_34 | AC | 226 ms
96,120 KB |
testcase_35 | AC | 403 ms
169,076 KB |
testcase_36 | AC | 356 ms
149,900 KB |
testcase_37 | AC | 152 ms
81,616 KB |
testcase_38 | AC | 237 ms
105,628 KB |
testcase_39 | AC | 173 ms
82,492 KB |
testcase_40 | AC | 180 ms
87,560 KB |
testcase_41 | AC | 151 ms
80,216 KB |
testcase_42 | AC | 205 ms
93,188 KB |
testcase_43 | AC | 224 ms
98,156 KB |
testcase_44 | AC | 111 ms
82,792 KB |
testcase_45 | AC | 107 ms
88,384 KB |
testcase_46 | AC | 224 ms
97,668 KB |
testcase_47 | AC | 254 ms
115,444 KB |
testcase_48 | AC | 338 ms
150,512 KB |
testcase_49 | AC | 398 ms
148,532 KB |
testcase_50 | AC | 546 ms
192,956 KB |
testcase_51 | AC | 163 ms
82,632 KB |
testcase_52 | AC | 744 ms
255,044 KB |
testcase_53 | AC | 323 ms
136,604 KB |
testcase_54 | AC | 169 ms
87,456 KB |
testcase_55 | AC | 580 ms
204,500 KB |
testcase_56 | AC | 114 ms
83,804 KB |
testcase_57 | AC | 471 ms
167,132 KB |
testcase_58 | AC | 361 ms
151,628 KB |
testcase_59 | AC | 178 ms
89,124 KB |
testcase_60 | AC | 151 ms
93,228 KB |
testcase_61 | AC | 250 ms
105,900 KB |
testcase_62 | AC | 435 ms
163,184 KB |
testcase_63 | AC | 278 ms
114,008 KB |
testcase_64 | AC | 1,658 ms
367,512 KB |
testcase_65 | AC | 213 ms
86,512 KB |
testcase_66 | AC | 936 ms
374,304 KB |
ソースコード
n,s,t,k=map(int,input().split()) x=[0]+list(map(int,input().split())) root=[[] for _ in range((n+3)*(k+3))] rev=[[] for _ in range((n+3)*(k+3))] start=x[s] def f(i,j): return i*(k+1)+j m=int(input()) for i in range(m): a,b,y=map(int,input().split()) for j in range(1,k): root[f(a,j)].append((f(b,j+1),y+x[b])) rev[f(b,j+1)].append((f(a,j),y+x[b])) root[f(a,k)].append((f(b,k),y+x[b])) rev[f(b, k)].append((f(a, k), y + x[b])) def dijkstra(N, G, s, INF=10 ** 18): """ https://tjkendev.github.io/procon-library/python/graph/dijkstra.html O((|E|+|V|)log|V|) V: 頂点数 G[v] = [(nod, cost)]: 頂点vから遷移可能な頂点(nod)とそのコスト(cost) s: 始点の頂点""" from heapq import heappush, heappop N+=1 dist = [INF] * N hp = [(start, s)] # (c, v) dist[s] = start while hp: c, v = heappop(hp) #vまで行くコストがc if dist[v] < c: continue for u, cost in G[v]: if dist[v] + cost < dist[u]: dist[u] = dist[v] + cost heappush(hp, (dist[u], u)) return dist dist=dijkstra((n+2)*(k+2),root,f(s,1)) if dist[f(t,k)]==10**18: print("Impossible") exit() print("Possible") print(dist[f(t,k)]) ans=[] now=f(t,k) while True: nod=now//(k+1) ans.append(nod) if now==f(s,1):break for node,cost in rev[now]: if dist[node]+cost==dist[now]: now=node break ans=ans[::-1] print(len(ans)) print(*ans)