結果

問題 No.3561 Collect KCPC
コンテスト
ユーザー みうね
提出日時 2026-05-28 11:28:53
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,986 ms / 6,000 ms
コード長 4,370 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 186 ms
コンパイル使用メモリ 85,324 KB
実行使用メモリ 151,484 KB
最終ジャッジ日時 2026-05-29 18:49:07
合計ジャッジ時間 27,242 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / 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
from heapq import heappush, heappop

def solve():
    # 入力を一括で読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    E = [[] 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])
        E[u].append((v, c))
        idx += 3
        
    S = input_data[idx]
    
    INF_DIST = 10**18
    INF_ID = 10**9
    INF_PAIR = (INF_DIST, INF_ID)
    
    # ==========================================
    # Phase 1: 'K' を起点とする最短経路 (D1)
    # ==========================================
    D1 = [INF_DIST] * N
    D1[0] = 0
    Q1 = [(0, 0)]
    
    while Q1:
        d, v = heappop(Q1)
        if d != D1[v]:
            continue
        for u, c in E[v]:
            if D1[u] > d + c:
                D1[u] = d + c
                heappush(Q1, (D1[u], u))
                
    for i in range(N):
        if S[i] != 'K':
            D1[i] = INF_DIST
        elif D1[i] != INF_DIST:
            heappush(Q1, (D1[i], i))
            
    while Q1:
        d, v = heappop(Q1)
        if d != D1[v]:
            continue
        for u, c in E[v]:
            if D1[u] > d + c:
                D1[u] = d + c
                heappush(Q1, (D1[u], u))
                
    # ==========================================
    # Phase 2: 'C' を起点とする最短経路 (D2, D3)
    # ==========================================
    D2 = [INF_PAIR] * N
    D3 = [INF_PAIR] * N
    Q2 = []
    
    for i in range(N):
        if S[i] == 'C' and D1[i] != INF_DIST:
            D2[i] = (D1[i], i)
            # 要素は (距離のタプル, 頂点)
            heappush(Q2, (D2[i], i)) 
            
    while Q2:
        d_pair, v = heappop(Q2)
        if d_pair != D2[v]:
            continue
        d_dist, d_id = d_pair
        for u, c in E[v]:
            nxt_pair = (d_dist + c, d_id)
            if D2[u] > nxt_pair:
                D2[u] = nxt_pair
                heappush(Q2, (D2[u], u))
            if D2[u][1] != d_id:
                if D3[u] > nxt_pair:
                    D3[u] = nxt_pair
                    
    for i in range(N):
        if D3[i] != INF_PAIR:
            heappush(Q2, (D3[i], i))
            
    while Q2:
        d_pair, v = heappop(Q2)
        if d_pair != D3[v]:
            continue
        d_dist, d_id = d_pair
        for u, c in E[v]:
            nxt_pair = (d_dist + c, d_id)
            if D2[u][1] != d_id and D3[u] > nxt_pair:
                D3[u] = nxt_pair
                heappush(Q2, (D3[u], u))
                
    # ==========================================
    # Phase 3: 'P' を起点とする最短経路 (D2, D3)
    # ==========================================
    for i in range(N):
        if S[i] != 'P':
            D2[i] = INF_PAIR
            D3[i] = INF_PAIR
        elif D2[i] != INF_PAIR:
            heappush(Q2, (D2[i], i))
            
    while Q2:
        d_pair, v = heappop(Q2)
        if d_pair != D2[v]:
            continue
        d_dist, d_id = d_pair
        for u, c in E[v]:
            nxt_pair = (d_dist + c, d_id)
            if D2[u] > nxt_pair:
                D2[u] = nxt_pair
                heappush(Q2, (D2[u], u))
            if D2[u][1] != d_id:
                if D3[u] > nxt_pair:
                    D3[u] = nxt_pair
                    
    for i in range(N):
        if D3[i] != INF_PAIR:
            heappush(Q2, (D3[i], i))
            
    while Q2:
        d_pair, v = heappop(Q2)
        if d_pair != D3[v]:
            continue
        d_dist, d_id = d_pair
        for u, c in E[v]:
            nxt_pair = (d_dist + c, d_id)
            if D2[u][1] != d_id and D3[u] > nxt_pair:
                D3[u] = nxt_pair
                heappush(Q2, (D3[u], u))
                
    # ==========================================
    # 解の計算
    # ==========================================
    ans = INF_DIST
    for i in range(N):
        if S[i] == 'C':
            if D2[i][1] != i:
                ans = min(ans, D2[i][0])
            else:
                ans = min(ans, D3[i][0])
                
    if ans > 10**17:
        ans = -1
        
    print(ans)

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