結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
ユーザー taiga0629kyopro
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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) #vc
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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0