結果

問題 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)  #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)
0