結果

問題 No.3561 Collect KCPC
コンテスト
ユーザー みうね
提出日時 2026-05-28 11:23:43
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 5,248 ms / 6,000 ms
コード長 2,767 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 525 ms
コンパイル使用メモリ 85,468 KB
実行使用メモリ 271,388 KB
最終ジャッジ日時 2026-05-29 18:48:33
合計ジャッジ時間 50,673 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 15
部分点2 20 % AC * 15
部分点3 20 % AC * 13
部分点4 50 % AC * 51
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# Geminiで翻訳

import sys
import heapq

def solve():
    # 入力を一括で読み込み (競技プログラミング向けの高速I/O)
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # グラフの構築
    graph = [[] for _ in range(N)]
    idx = 2
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        c = int(input_data[idx+2])
        graph[u].append((v, c))
        idx += 3
        
    S = input_data[idx]
    
    # dist[u][s] は 最大2つの (cost, id) のリストを持つ
    # 異なる頂点で 'C' を2回踏む必要があるため、状態の上位2つを保持する
    dist = [[[] for _ in range(5)] for _ in range(N)]
    
    def update(u, s, c, id_val):
        d = dist[u][s]
        for i, p in enumerate(d):
            if p[1] == id_val:
                if c < p[0]:
                    d[i] = (c, id_val)
                    d.sort()
                    return True
                return False
                
        d.append((c, id_val))
        d.sort()
        if len(d) > 2:
            d.pop()
            
        for p in d:
            if p[1] == id_val:
                return True
        return False

    # 優先度付きキュー (cost, u, state, id)
    pq = []
    update(0, 0, 0, -1)
    heapq.heappush(pq, (0, 0, 0, -1))
    
    while pq:
        cost, u, s, id_val = heapq.heappop(pq)
        
        # 枝刈り (Lazy Deletion)
        valid = False
        for p in dist[u][s]:
            if p[0] == cost and p[1] == id_val:
                valid = True
                break
        if not valid:
            continue
            
        # 隣接頂点への移動
        for v, edge_cost in graph[u]:
            if update(v, s, cost + edge_cost, id_val):
                heapq.heappush(pq, (cost + edge_cost, v, s, id_val))
                
        # 状態の遷移 (K -> C -> P -> C)
        ns = -1
        nid = id_val
        
        if s == 0 and S[u] == 'K':
            ns = 1
        elif s == 1 and S[u] == 'C':
            ns = 2
            nid = u
        elif s == 2 and S[u] == 'P':
            ns = 3
        elif s == 3 and S[u] == 'C' and u != id_val:
            ns = 4
            
        if ns != -1:
            if update(u, ns, cost, nid):
                heapq.heappush(pq, (cost, u, ns, nid))
                
    # 答えの計算 (状態4に到達している頂点の中での最小コストを探す)
    ans = float('inf')
    for i in range(N):
        if dist[i][4]:
            ans = min(ans, dist[i][4][0][0])
            
    print(-1 if ans == float('inf') else ans)

if __name__ == '__main__':
    solve()
0