結果

問題 No.3561 Collect KCPC
コンテスト
ユーザー LyricalMaestro
提出日時 2026-06-21 03:02:25
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,733 ms / 6,000 ms
コード長 4,097 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 281 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 192,800 KB
最終ジャッジ日時 2026-06-21 03:03:14
合計ジャッジ時間 37,721 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 15
部分点2 20 % AC * 15
部分点3 20 % AC * 13
部分点4 50 % AC * 51
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/3561

import heapq

MAX_INT = 10 ** 18

def main():
    N, M = map(int, input().split())
    next_nodes = [[] for _ in range(N)]
    for _ in range(M):
        u, v, c = map(int, input().split())
        next_nodes[u - 1].append((v - 1, c))
    S = input()


    fix = [[MAX_INT for _ in range(N)] for _ in range(2)]
    seen = [[MAX_INT for _ in range(N)] for _ in range(2)]
    queue = []

    seen[0][0] = 0
    heapq.heappush(queue, (0, 0, 0))
    c_map = {}
    while len(queue) > 0:
        cost, state, v = heapq.heappop(queue)
        if fix[state][v] < MAX_INT:
            continue

        fix[state][v] = cost
        if state == 0 and S[v] == "K":
            new_state = 1
            if fix[new_state][v] == MAX_INT:
                if seen[new_state][v] > cost:
                    seen[new_state][v] = cost
                    heapq.heappush(queue, (cost, new_state, v))
        
        for w, c in next_nodes[v]:
            if fix[state][w] < MAX_INT:
                continue

            new_cost = c + cost
            if seen[state][w] > new_cost:
                seen[state][w] = new_cost
                heapq.heappush(queue, (new_cost, state, w))

    x_map = []
    for i in range(N):
        if fix[1][i] < MAX_INT and S[i] == "C":
            x_map.append((i, fix[1][i]))
    
    fix = [[[MAX_INT, MAX_INT, MAX_INT, MAX_INT] for _ in range(N)] for _ in range(2)]
    seen = [[[MAX_INT, MAX_INT, MAX_INT, MAX_INT] for _ in range(N)] for _ in range(2)]
    queue = []
    
    for index,  cost in x_map:
        heapq.heappush(queue, (cost, 0, index, index))
        seen[0][index][0] = cost
        seen[0][index][1] = index

    def update(fix, seen, new_state, start_v, w, cost):
        if fix[new_state][w][0] == MAX_INT:
            if seen[new_state][w][0] > cost:
                if seen[new_state][w][1] == start_v:
                    seen[new_state][w][0] = cost
                    seen[new_state][w][1] = start_v
                    heapq.heappush(queue, (cost, new_state, start_v, w))
                else:
                    seen[new_state][w][2] = seen[new_state][w][0]
                    seen[new_state][w][3] = seen[new_state][w][1]
                    seen[new_state][w][0] = cost
                    seen[new_state][w][1] = start_v
                    heapq.heappush(queue, (cost, new_state, start_v, w))
            elif seen[new_state][w][1] != start_v and seen[new_state][w][2] > cost:
                seen[new_state][w][2] = cost
                seen[new_state][w][3] = start_v
                heapq.heappush(queue, (cost, new_state, start_v, w))
        elif fix[new_state][w][1] != start_v and fix[new_state][w][2]== MAX_INT:
            if seen[new_state][w][2] > cost:
                seen[new_state][w][2] = cost
                seen[new_state][w][3] = start_v
                heapq.heappush(queue, (cost, new_state, start_v, w))
    
    while len(queue) > 0:
        cost, state, start_v, v = heapq.heappop(queue)

        if fix[state][v][0] == MAX_INT:
            fix[state][v][0] = cost
            fix[state][v][1] = start_v
        elif fix[state][v][1] != start_v and fix[state][v][2] == MAX_INT:
            fix[state][v][2] = cost
            fix[state][v][3] = start_v
        else:
            continue

        if state == 0 and S[v] == "P":
            new_state = 1
            w = v
            update(fix, seen, new_state, start_v, w, cost)


        for w, c in next_nodes[v]:
            new_cost = c + cost
            update(fix, seen, state, start_v, w, new_cost)

    answer = MAX_INT
    for i in range(N):
        if S[i] == "C":
            if fix[1][i][0] < MAX_INT and fix[1][i][1] != i:
                answer = min(answer, fix[1][i][0])
                continue

            if fix[1][i][2] < MAX_INT and fix[1][i][3] != i:
                answer = min(answer, fix[1][i][2])
                continue
    if answer == MAX_INT:
        print(-1)
    else:
        print(answer)
            


            

             














if __name__ == "__main__":
    main()
0