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

• 問題: No.3561 Collect KCPC
• ユーザー: jastaway
• 提出日時: 2026-05-28 12:10:03
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 453 ms / 6,000 ms
• コード長: 4,577 bytes
• コンパイル時間: 12,967 ms
• コンパイル使用メモリ: 460,708 KB
• 実行使用メモリ: 43,776 KB
• 最終ジャッジ日時: 2026-05-29 18:49:07
• 合計ジャッジ時間: 24,006 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

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

ソースコード

#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MIN_N = 4;
const int MAX_N = 100'000;
const int MAX_M = 150'000;
const ll MAX_C = 1'000'000'000;

const ll INF = 1LL << 60;
using p2 = pair<ll, int>;
template<class T, class U> bool chmin(T& a, U b) { return a > b ? a = b, 1 : 0; }

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);
    int N = inf.readInt(MIN_N, MAX_N, "N");
    inf.readSpace();
    int M = inf.readInt(1, MAX_M, "M");
    inf.readEoln();
    vector<vector<pair<int, ll>>> G(N), rG(N);
    vector<pair<int, int>> uvs(M);
    for(int i = 0; i < M; i++)
    {
        int u = inf.readInt(1, N, "U_"+to_string(i));
        inf.readSpace();
        int v = inf.readInt(1, N, "V_"+to_string(i));
        inf.readSpace();
        ll c = inf.readLong(1, MAX_C, "C_"+to_string(i));
        inf.readEoln();
        inf.ensuref(u != v, "U_i not V_i");
        u--; v--;
        G[u].emplace_back(v, c);
        rG[v].emplace_back(u, c);
        uvs[i] = {u, v};
    }
    sort(uvs.begin(), uvs.end());
    for(int i = 0; i < M - 1; i++) inf.ensuref(uvs[i] != uvs[i + 1], "(U_i, V_i) not (U_j, V_j)");
    string S = inf.readString(format("[A-Z]{%d,%d}", N, N), "S");
    inf.readEof();
    vector<ll> d1(N, INF);
    {
        priority_queue<p2, vector<p2>, greater<p2>> pq;
        d1[0] = 0;
        pq.emplace(0, 0);
        while(!pq.empty())
        {
            auto [d, n] = pq.top(); pq.pop();
            if(d1[n] < d) continue;
            for(auto [e, c] : G[n])
            {
                if(chmin(d1[e], d1[n] + c)) pq.emplace(d1[e], e);
            }
        }
    }
    vector<ll> dK(N, INF);
    {
        priority_queue<p2, vector<p2>, greater<p2>> pq;
        for(int i = 0; i < N; i++) if(S[i] == 'K')
        {
            dK[i] = d1[i];
            pq.emplace(d1[i], i);
        }
        while(!pq.empty())
        {
            auto [d, n] = pq.top(); pq.pop();
            if(dK[n] < d) continue;
            for(auto [e, c] : G[n])
            {
                if(chmin(dK[e], dK[n] + c)) pq.emplace(dK[e], e);
            }
        }
    }
    vector<pair<p2, p2>> dP1(N, {p2{INF, -1}, p2{INF, -1}}), dP2(N, {p2{INF, -1}, p2{INF, -1}});
    {
        priority_queue<pair<p2, int>, vector<pair<p2, int>>, greater<pair<p2, int>>> pq;
        for(int i = 0; i < N; i++) if(S[i] == 'C' && dK[i] < INF)
        {
            dP1[i].first = {dK[i], i};
            pq.emplace(p2{dK[i], i}, i);
        }
        while(!pq.empty())
        {
            auto [di, n] = pq.top(); pq.pop();
            auto [d, i] = di;
            if(dP1[n].second.first < d) continue;
            for(auto [e, c] : G[n])
            {
                if(dP1[e].first.first > d + c)
                {
                    if(dP1[e].first.second != i) dP1[e].second = dP1[e].first;
                    dP1[e].first = {d + c, i};
                    pq.emplace(p2{d + c, i}, e);
                }
                else if(dP1[e].second.first > d + c && dP1[e].first.second != i)
                {
                    dP1[e].second = {d + c, i};
                    pq.emplace(p2{d + c, i}, e);
                }
            }
        }
        for(int i = 0; i < N; i++) if(S[i] == 'C')
        {
            dP2[i].first = {0, i};
            pq.emplace(p2{0, i}, i);
        }
        while(!pq.empty())
        {
            auto [di, n] = pq.top(); pq.pop();
            auto [d, i] = di;
            if(dP2[n].second.first < d) continue;
            for(auto [e, c] : rG[n])
            {
                if(dP2[e].first.first > d + c)
                {
                    if(dP2[e].first.second != i) dP2[e].second = dP2[e].first;
                    dP2[e].first = {d + c, i};
                    pq.emplace(p2{d + c, i}, e);
                }
                else if(dP2[e].second.first > d + c && dP2[e].first.second != i)
                {
                    dP2[e].second = {d + c, i};
                    pq.emplace(p2{d + c, i}, e);
                }
            }
        }
    }
    ll ans = INF;
    for(int i = 0; i < N; i++) if(S[i] == 'P')
    {
        auto [pi1, pi2] = dP1[i];
        auto [p1, i1] = pi1;
        auto [p2, i2] = pi2;
        auto [qj1, qj2] = dP2[i];
        auto [q1, j1] = qj1;
        auto [q2, j2] = qj2;
        if(i1 != j1) chmin(ans, p1 + q1);
        if(i1 != j2) chmin(ans, p1 + q2);
        if(i2 != j1) chmin(ans, p2 + q1);
        if(i2 != j2) chmin(ans, p2 + q2);
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
}