結果

問題 No.3561 Collect KCPC
コンテスト
ユーザー yuunegi
提出日時 2026-05-31 16:59:57
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 236 ms / 6,000 ms
コード長 5,384 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,301 ms
コンパイル使用メモリ 345,656 KB
実行使用メモリ 20,660 KB
最終ジャッジ日時 2026-05-31 17:00:09
合計ジャッジ時間 10,112 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 15
部分点2 20 % AC * 15
部分点3 20 % AC * 13
部分点4 50 % AC * 51
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

long long INF=1e18;

struct S{
    array<array<long long,2>,6>data={{{INF,-1},{INF,-1},{INF,-1},{INF,-1},{INF,-1},{INF,-1}}};
};

int main(void){
    int n,m;
    cin>>n>>m;
    vector<array<int,2>>v[100000];
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a-1].push_back({b-1,c});
    }
    string s;
    cin>>s;
    vector<S>vis(n);
    priority_queue<array<long long,4>>pq;
    if(s[0]=='K'){
        pq.push({0,0,1,-1});
        vis[0].data[1][0]=0;
    }else{
        pq.push({0,0,0,-1});
        vis[0].data[0][0]=0;
    }
    long long ans=INF;
    while(!pq.empty()){
        long long val=-pq.top()[0],now=pq.top()[1],cond=pq.top()[2],cd=pq.top()[3];
        //cout<<val<<" "<<now+1<<" "<<cond<<" "<<cd+1<<endl;
        pq.pop();
        if(cond==0){
            if(val!=vis[now].data[0][0])continue;
        }else if(cond==1){
            if(val!=vis[now].data[1][0])continue;
        }else if(cond==2){
            if((val!=vis[now].data[2][0]||cd!=vis[now].data[2][1])&&(val!=vis[now].data[3][0]||cd!=vis[now].data[3][1]))continue;
        }else if(cond==3){
            if((val!=vis[now].data[4][0]||cd!=vis[now].data[4][1])&&(val!=vis[now].data[5][0]||cd!=vis[now].data[5][1]))continue;
        }
        //cout<<val<<" "<<now+1<<" "<<cond<<" "<<cd+1<<endl;
        for(int i=0;i<(int)v[now].size();i++){
            int nx=v[now][i][0];
            long long v2=v[now][i][1];
            //cout<<s[now]<<s[nx];
            if(cond==0&&s[nx]=='K'){
                if(vis[nx].data[1][0]>v2+val){
                    vis[nx].data[1][0]=v2+val;
                    pq.push({-(v2+val),nx,1,-1});
                }
            }else if(cond==1&&s[nx]=='C'){
                if(vis[nx].data[2][0]>v2+val){
                    if(vis[nx].data[2][1]==nx){
                        vis[nx].data[2][0]=v2+val;
                        pq.push({-(v2+val),nx,2,nx});
                    }else{
                        swap(vis[nx].data[2],vis[nx].data[3]);
                        vis[nx].data[2][0]=v2+val;
                        vis[nx].data[2][1]=nx;
                        pq.push({-(v2+val),nx,2,nx});
                    }
                }else if(vis[nx].data[2][1]!=nx&&vis[nx].data[3][0]>v2+val){
                    vis[nx].data[3][0]=v2+val;
                    vis[nx].data[3][1]=nx;
                    pq.push({-(v2+val),nx,2,nx});
                }
            }else if(cond==2&&s[nx]=='P'){
                if(vis[nx].data[4][0]>v2+val){
                    if(vis[nx].data[4][1]==cd){
                        vis[nx].data[4][0]=v2+val;
                        pq.push({-(v2+val),nx,3,cd});
                    }else{
                        swap(vis[nx].data[4],vis[nx].data[5]);
                        vis[nx].data[4][0]=v2+val;
                        vis[nx].data[4][1]=cd;
                        pq.push({-(v2+val),nx,3,cd});
                    }
                }else if(vis[nx].data[4][1]!=cd&&vis[nx].data[5][0]>v2+val){
                    vis[nx].data[5][0]=v2+val;
                    vis[nx].data[5][1]=cd;
                    pq.push({-(v2+val),nx,3,cd});
                }
            }else if(cond==3&&s[nx]=='C'&&nx!=cd){
                ans=min(ans,v2+val);
            }else if(cond==0){
                if(vis[nx].data[0][0]>v2+val){
                    vis[nx].data[0][0]=v2+val;
                    pq.push({-(v2+val),nx,0,-1});
                }
            }else if(cond==1){
                if(vis[nx].data[1][0]>v2+val){
                    vis[nx].data[1][0]=v2+val;
                    pq.push({-(v2+val),nx,1,-1});
                }
            }else if(cond==2){
                if(vis[nx].data[2][0]>v2+val){
                    if(vis[nx].data[2][1]==cd){
                        vis[nx].data[2][0]=v2+val;
                        pq.push({-(v2+val),nx,2,cd});
                    }else{
                        swap(vis[nx].data[2],vis[nx].data[3]);
                        //cout<<"~";
                        vis[nx].data[2][0]=v2+val;
                        vis[nx].data[2][1]=cd;
                        pq.push({-(v2+val),nx,2,cd});
                    }
                }else if(vis[nx].data[2][1]!=cd&&vis[nx].data[3][0]>v2+val){
                    vis[nx].data[3][0]=v2+val;
                    vis[nx].data[3][1]=cd;
                    pq.push({-(v2+val),nx,2,cd});
                }
                //cout<<"^";
            }else if(cond==3){
                if(vis[nx].data[4][0]>v2+val){
                    if(vis[nx].data[4][1]==cd){
                        vis[nx].data[4][0]=v2+val;
                        pq.push({-(v2+val),nx,3,cd});
                    }else{
                        swap(vis[nx].data[4],vis[nx].data[5]);
                        vis[nx].data[4][0]=v2+val;
                        vis[nx].data[4][1]=cd;
                        pq.push({-(v2+val),nx,3,cd});
                    }
                }else if(vis[nx].data[4][1]!=cd&&vis[nx].data[5][0]>v2+val){
                    vis[nx].data[5][0]=v2+val;
                    vis[nx].data[5][1]=cd;
                    pq.push({-(v2+val),nx,3,cd});
                }
            }
        }
        //cout<<vis[1].data[2][0]<<" "<<vis[1].data[2][1]<<" "<<vis[1].data[3][0]<<" "<<vis[1].data[3][1]<<"!"<<endl;
    }
    cout<<(ans==INF?-1:ans)<<endl;
    return 0;
}
0