結果
問題 | 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)+jm=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.htmlO((|E|+|V|)log|V|)V: 頂点数G[v] = [(nod, cost)]:頂点vから遷移可能な頂点(nod)とそのコスト(cost)s: 始点の頂点"""from heapq import heappush, heappopN+=1dist = [INF] * Nhp = [(start, s)] # (c, v)dist[s] = startwhile hp:c, v = heappop(hp) #vまで行くコストがcif dist[v] < c:continuefor u, cost in G[v]:if dist[v] + cost < dist[u]:dist[u] = dist[v] + costheappush(hp, (dist[u], u))return distdist=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):breakfor node,cost in rev[now]:if dist[node]+cost==dist[now]:now=nodebreakans=ans[::-1]print(len(ans))print(*ans)