結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
ユーザー 👑 SPD_9X2SPD_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
53,680 KB
testcase_01 AC 47 ms
53,632 KB
testcase_02 AC 49 ms
53,444 KB
testcase_03 AC 45 ms
53,380 KB
testcase_04 AC 428 ms
186,424 KB
testcase_05 AC 2,126 ms
330,016 KB
testcase_06 AC 599 ms
170,364 KB
testcase_07 AC 565 ms
166,156 KB
testcase_08 AC 1,316 ms
197,540 KB
testcase_09 AC 347 ms
105,088 KB
testcase_10 AC 178 ms
102,128 KB
testcase_11 AC 878 ms
202,416 KB
testcase_12 AC 1,586 ms
282,020 KB
testcase_13 AC 398 ms
133,640 KB
testcase_14 AC 563 ms
205,208 KB
testcase_15 AC 171 ms
88,520 KB
testcase_16 AC 785 ms
259,208 KB
testcase_17 AC 180 ms
81,572 KB
testcase_18 AC 600 ms
115,912 KB
testcase_19 AC 652 ms
162,896 KB
testcase_20 AC 345 ms
106,856 KB
testcase_21 AC 1,179 ms
305,672 KB
testcase_22 AC 430 ms
179,696 KB
testcase_23 AC 458 ms
105,056 KB
testcase_24 AC 162 ms
82,204 KB
testcase_25 AC 193 ms
87,044 KB
testcase_26 AC 78 ms
72,360 KB
testcase_27 AC 176 ms
82,420 KB
testcase_28 AC 208 ms
89,696 KB
testcase_29 AC 159 ms
85,928 KB
testcase_30 AC 161 ms
85,744 KB
testcase_31 AC 192 ms
87,292 KB
testcase_32 AC 153 ms
80,864 KB
testcase_33 AC 193 ms
89,528 KB
testcase_34 AC 194 ms
86,968 KB
testcase_35 AC 330 ms
116,360 KB
testcase_36 AC 270 ms
105,832 KB
testcase_37 AC 123 ms
78,764 KB
testcase_38 AC 197 ms
91,384 KB
testcase_39 AC 150 ms
79,820 KB
testcase_40 AC 150 ms
82,256 KB
testcase_41 AC 125 ms
78,296 KB
testcase_42 AC 169 ms
85,276 KB
testcase_43 AC 191 ms
87,080 KB
testcase_44 AC 87 ms
82,452 KB
testcase_45 AC 97 ms
97,308 KB
testcase_46 AC 228 ms
94,444 KB
testcase_47 AC 277 ms
111,684 KB
testcase_48 AC 458 ms
166,464 KB
testcase_49 AC 411 ms
137,620 KB
testcase_50 AC 652 ms
187,704 KB
testcase_51 AC 154 ms
80,692 KB
testcase_52 AC 842 ms
218,700 KB
testcase_53 AC 341 ms
134,428 KB
testcase_54 AC 156 ms
84,256 KB
testcase_55 AC 618 ms
183,784 KB
testcase_56 AC 93 ms
83,720 KB
testcase_57 AC 512 ms
152,752 KB
testcase_58 AC 383 ms
139,580 KB
testcase_59 AC 170 ms
87,304 KB
testcase_60 AC 142 ms
97,408 KB
testcase_61 AC 229 ms
98,084 KB
testcase_62 AC 435 ms
141,400 KB
testcase_63 AC 316 ms
104,472 KB
testcase_64 AC 1,594 ms
319,864 KB
testcase_65 AC 187 ms
84,476 KB
testcase_66 AC 1,177 ms
429,424 KB
権限があれば一括ダウンロードができます

ソースコード

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