結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2021-06-11 21:54:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,126 ms / 3,000 ms
コード長 2,008 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 429,424 KB
最終ジャッジ日時 2024-12-14 23:24:01
合計ジャッジ時間 37,061 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 67
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

S -> T
のパスを作る

頂点にも重みがある
結局 N*K が小さい
ので
Dijkstraで行けそう？

in,out,層
の3次元必要

各Kに関して、2N個いる。

2NK + v + (N <- outは足す)

"""

from sys import stdin

import heapq
def Dijkstra(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    end_flag = [False] * len(lis)
    end_num = 0

    plis = [i for i in range(len(lis))]
    
    q = [(0,start)]

    while len(q) > 0:

        ncost,now = heapq.heappop(q)

        if end_flag[now]:
            continue

        end_flag[now] = True
        end_num += 1

        if end_num == len(lis):
            break

        for nex,ecost in lis[now]:

            if ret[nex] > ncost + ecost:
                ret[nex] = ncost + ecost
                heapq.heappush(q , (ret[nex] , nex))
                plis[nex] = now

    return ret,plis

#io == 0 == in
#io == 1 == out

def enc(v,k,io):
    if io == 0:
        return 2*N*k + v
    else:
        return 2*N*k + v + N

def dec(x):
    v = x % N
    io = (x//N) % 2
    k = (x//(2*N))
    return v,k,io

N,S,T,K = map(int,stdin.readline().split())
X = list(map(int,stdin.readline().split()))
S -= 1
T -= 1

st = enc(S,0,0)
go = enc(T,K-1,1)

lis = [ [] for i in range(N*(K)*2) ]
for k in range(K):
    for v in range(N):
        vs = enc(v,k,0)
        vg = enc(v,k,1)
        lis[vs].append( (vg,X[v]) )

M = int(stdin.readline())
for i in range(M):
    A,B,Y = map(int,stdin.readline().split())
    A -= 1
    B -= 1

    for k in range(K-1):
        lis[enc(A,k,1)].append( (enc(B,k+1,0),Y) )

    lis[enc(A,K-1,1)].append( (enc(B,K-1,0),Y) )

dlis,plis = Dijkstra(lis,st)
if dlis[go] == float("inf"):
    print ("Impossible")
else:
    print ("Possible")
    print (dlis[go])
    ans = [go]

    v = go
    while v != st:
        ans.append(plis[v])
        v = plis[v]

    anst = []
    for i in ans:
        anst.append(dec(i)[0] + 1)

    anst.reverse()
    print (len(anst)//2)
    print (*anst[::2])
0