結果
問題 | No.1545 [Cherry 2nd Tune N] Anthem |
ユーザー |
![]() |
提出日時 | 2021-06-11 22:07:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,957 ms / 3,000 ms |
コード長 | 1,543 bytes |
コンパイル時間 | 411 ms |
コンパイル使用メモリ | 82,092 KB |
実行使用メモリ | 373,492 KB |
最終ジャッジ日時 | 2024-12-14 23:54:52 |
合計ジャッジ時間 | 35,760 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 67 |
ソースコード
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)