#1166590 (C++23) No.3561 Collect KCPC

• 問題: No.3561 Collect KCPC
• ユーザー: TKTYI
• 提出日時: 2026-05-25 05:44:19
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 4,209 bytes
• コンパイル時間: 4,088 ms
• コンパイル使用メモリ: 362,448 KB
• 実行使用メモリ: 16,268 KB
• 最終ジャッジ日時: 2026-05-29 18:37:54
• 合計ジャッジ時間: 15,656 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_1

サブタスク	配点	結果
部分点1	10 %	AC * 1 RE * 14
部分点2	20 %	AC * 1 RE * 14
部分点3	20 %	AC * 13
部分点4	50 %	AC * 13 RE * 38
合計	20 点

ソースコード

#include <bits/stdc++.h>
using namespace std;

template <typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int N, M;
    cin >> N >> M;
    assert(4 <= N && N <= 200'000);
    assert(1 <= M && M <= 300'000);
    vector<vector<pair<int, int>>> E(N);
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        assert(1 <= min(u, v) && max(u, v) <= N);
        assert(u != v);
        assert(1 <= c && c<= 1'000'000'000);
        u--; v--;
        E[u].emplace_back(v, c);
        assert(u < v);
    }
    for (int i = 0; i < N; i++) {
        sort(E[i].begin(), E[i].end());
        for (int j = 0; j + 1 < E[i].size(); j++) {
            assert(E[i][j].first != E[i][j + 1].first);
        }
    }
    string S;
    cin>>S;
    assert(S.size() == N);
    for (auto c : S) assert('A' <= c && c <= 'Z');

    vector<long long> D1(N, 1e18);
    D1[0] = 0;
    min_priority_queue<pair<long long, int>> Q1;
    Q1.emplace(D1[0], 0);
    while (!Q1.empty()) {
        auto [d, v] = Q1.top();
        Q1.pop();
        if (d != D1[v]) continue;
        for (auto [u, c] : E[v]) if (D1[u] > d + c) {
            D1[u] = d + c;
            Q1.emplace(D1[u], u);
        }
    }
    for (int i = 0; i < N; i++) {
        if(S[i] != 'K') D1[i] = 1e18;
        else Q1.emplace(D1[i], i);
    }
    while (!Q1.empty()) {
        auto [d, v] = Q1.top();
        Q1.pop();
        if (d != D1[v]) continue;
        for (auto [u, c] : E[v]) if (D1[u] > d + c) {
            D1[u] = d + c;
            Q1.emplace(D1[u], u);
        }
    }

    vector<pair<long long, int>> D2(N, make_pair(1e18, 1e9));
    vector<pair<long long, int>> D3(N, make_pair(1e18, 1e9));
    min_priority_queue<pair<pair<long long, int>, int>> Q2;
    for (int i = 0; i < N; i++) if (S[i] == 'C') {
        D2[i].first = D1[i];
        D2[i].second = i;
        Q2.emplace(D2[i], i);
    }
    while (!Q2.empty()) {
        auto [d, v] = Q2.top();
        Q2.pop();
        if (d != D2[v]) continue;
        for (auto [u, c] : E[v]) {
            if (D2[u] > make_pair(d.first + c, d.second)) {
                D2[u].first = d.first + c;
                D2[u].second = d.second;
                Q2.emplace(D2[u], u);
            }
            if (D2[u].second != d.second) {
                D3[u] =min(D3[u], {d.first + c, d.second});
            }
        }
    }
    for (int i = 0; i < N; i++) Q2.emplace(D3[i], i);
    while (!Q2.empty()) {
        auto [d, v] = Q2.top();
        Q2.pop();
        if (d != D3[v]) continue;
        for (auto [u, c] : E[v]) {
            if (D2[u].second != d.second && D3[u] > make_pair(d.first + c, d.second)) {
                D3[u].first = d.first + c;
                D3[u].second = d.second;
                Q2.emplace(D3[u], u);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        if(S[i] != 'P') D2[i] = D3[i] = {1e18, 1e9};
        else Q2.emplace(D2[i], i);
    }
    while (!Q2.empty()) {
        auto [d, v] = Q2.top();
        Q2.pop();
        if (d != D2[v]) continue;
        for (auto [u, c] : E[v]) {
            if (D2[u] > make_pair(d.first + c, d.second)) {
                D2[u].first = d.first + c;
                D2[u].second = d.second;
                Q2.emplace(D2[u], u);
            }
            if (D2[u].second != d.second) {
                D3[u] =min(D3[u], {d.first + c, d.second});
            }
        }
    }
    for (int i = 0; i < N; i++) Q2.emplace(D3[i], i);
    while (!Q2.empty()) {
        auto [d, v] = Q2.top();
        Q2.pop();
        if (d != D3[v]) continue;
        for (auto [u, c] : E[v]) {
            if (D2[u].second != d.second && D3[u] > make_pair(d.first + c, d.second)) {
                D3[u].first = d.first + c;
                D3[u].second = d.second;
                Q2.emplace(D3[u], u);
            }
        }
    }
    long long ans = 1e18;
    for (int i = 0; i < N; i++) if (S[i] == 'C'){
        if (D2[i].second != i) ans = min(ans, D2[i].first);
        else ans = min(ans, D3[i].first);
    }
    if (ans > 1e17) ans = -1;
    cout << ans << endl;
    return 0;
}