結果

問題 No.3561 Collect KCPC
コンテスト
ユーザー titia
提出日時 2026-06-04 07:24:14
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 3,109 ms / 6,000 ms
コード長 4,014 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 315 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 185,516 KB
最終ジャッジ日時 2026-06-04 07:24:54
合計ジャッジ時間 35,233 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 15
部分点2 20 % AC * 15
部分点3 20 % AC * 13
部分点4 50 % AC * 51
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from heapq import heappop,heappush

N,M=list(map(int,input().split()))

E=[[] for i in range(N)]

for i in range(M):
    x,y,c=list(map(int,input().split()))
    x-=1
    y-=1
    E[x].append((y,c))

S=input().strip()

DP=[[(1<<63,-1) for j in range(N)] for i in range(7)]
DP[0][0]=(0,-1)
Q=[]
Q.append((0,0,0,-100))

while Q:
    time,dpind,ind,useind=heappop(Q)

    if DP[dpind][ind][0]!=time:
        continue

    if dpind==0 and S[ind]=="K":
        if DP[dpind+1][ind][0]>time:
            DP[dpind+1][ind]=(time,ind)
            heappush(Q,(time,dpind+1,ind,useind))

    if dpind==1 and S[ind]=="C":
        if DP[2][ind][0]>time:
            if DP[2][ind][1]==useind:
                DP[2][ind]=(time,ind)
                heappush(Q,(time,2,ind,ind))
            else:
                DP[3][ind]=DP[2][ind]
                DP[2][ind]=(time,ind)
                heappush(Q,(time,dpind+1,ind,ind))

                if DP[2][ind][1]!=DP[3][ind][1] and DP[3][ind][0]!=1<<63:
                    heappush(Q,(DP[3][ind][0],3,ind,DP[3][ind][1]))
                else:
                    DP[3][ind]=(1<<63,-1)
                    
        elif DP[3][ind][0]>time and useind!=DP[2][ind][1]:
            DP[3][ind]=(time,ind)
            heappush(Q,(time,3,ind,ind))

    if (dpind==2 or dpind==3) and S[ind]=="P":
        if DP[4][ind][0]>time:
            if DP[4][ind][1]==useind:
                DP[4][ind]=(time,ind)
                heappush(Q,(time,4,ind,useind))
            else:
                DP[5][ind]=DP[4][ind]
                DP[4][ind]=(time,useind)
                heappush(Q,(time,4,ind,useind))

                if DP[4][ind][1]!=DP[5][ind][1]:
                    heappush(Q,(DP[5][ind][0],5,ind,DP[5][ind][1]))
                else:
                    DP[5][ind]=(1<<63,-1)
            
        elif DP[5][ind][0]>time and DP[4][ind][1]!=useind:
            DP[5][ind]=(time,useind)
            heappush(Q,(time,5,ind,useind))

    if (dpind==4 or dpind==5) and S[ind]=="C":
        if DP[6][ind][0]>time and ind!=useind:
            DP[6][ind]=(time,ind)

    for to,cost in E[ind]:
        if dpind<=1:
            if DP[dpind][to][0]>time+cost:
                DP[dpind][to]=(time+cost,useind)
                heappush(Q,(time+cost,dpind,to,useind))

        if dpind==2 or dpind==3:
            if DP[2][to][0]>time+cost:
                if useind==DP[2][to][1]:
                    DP[2][to]=(time+cost,useind)
                    heappush(Q,(DP[2][to][0],2,to,DP[2][to][1]))
                else:
                    DP[3][to]=DP[2][to]
                    DP[2][to]=(time+cost,useind)

                    heappush(Q,(DP[2][to][0],2,to,DP[2][to][1]))

                    if DP[3][to][0]!=1<<63:
                        heappush(Q,(DP[3][to][0],3,to,DP[3][to][1]))

                    else:
                        DP[3][to]=(1<<63,-1)

            elif DP[3][to][0]>time+cost and useind!=DP[2][to][1]:
                DP[3][to]=(time+cost,useind)
                heappush(Q,(DP[3][to][0],3,to,DP[3][to][1]))

        if dpind==4 or dpind==5:
            if DP[4][to][0]>time+cost:
                if useind==DP[4][to][1]:
                    DP[4][to]=(time+cost,useind)
                    heappush(Q,(DP[4][to][0],4,to,DP[4][to][1]))
                else:                       
                    DP[5][to]=DP[4][to]
                    DP[4][to]=(time+cost,useind)

                    heappush(Q,(DP[4][to][0],4,to,DP[4][to][1]))

                    if DP[5][to][0]!=1<<63:
                        heappush(Q,(DP[5][to][0],5,to,DP[5][to][1]))

                    else:
                        DP[5][to]=(1<<63,-1)

            elif DP[5][to][0]>time+cost and useind!=DP[4][to][1]:
                DP[5][to]=(time+cost,useind)
                heappush(Q,(DP[5][to][0],5,to,DP[5][to][1]))

                

#for x in DP:
#    print(x)

ANS=1<<63

for x,c in DP[6]:
    ANS=min(ANS,x)

if ANS==1<<63:
    print(-1)
else:
    print(ANS)
0