結果

問題 No.3561 Collect KCPC
コンテスト
ユーザー 蜜蜂
提出日時 2026-05-29 19:17:30
言語 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  
実行時間 4,794 ms / 6,000 ms
コード長 3,192 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,083 ms
コンパイル使用メモリ 360,404 KB
実行使用メモリ 20,656 KB
最終ジャッジ日時 2026-05-29 19:18:16
合計ジャッジ時間 32,730 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge4_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 15
部分点2 20 % AC * 15
部分点3 20 % AC * 13
部分点4 50 % AC * 51
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// g++-15 1.cpp -std=c++23 -O2 -I .

// 壊れるとき
// conda deactivate    # 何回か必要なことあり
// hash -r             # コマンドキャッシュクリア
// which -a ld
// ld の先頭が /usr/bin/ld になればそのままコンパイルしてOK


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

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;

#include <atcoder/math>
#include <atcoder/modint>
using namespace atcoder;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

template <typename S, typename T>
istream& operator>>(istream& is, pair<S, T> &v){
  is >> v.first >> v.second;
  return is;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, pair<S, T> &v){
  os << v.first << " " << v.second << "\n";
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T> &v){
  for(T &e: v) is >> e;
  return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T> v){
  for(int i=0;i<v.size()-1;i++)os<<v[i]<<" ";
  os<<v.back()<<"\n";
  return os;
}

random_device seed;
mt19937_64 randint(seed());

ll grr(ll mi, ll ma) { // [mi, ma)
    return mi + randint() % (ma - mi);
}

// KClc
ll work(int n,vector<vector<pair<int,ll>>> &g,string &s){
  // cout<<s<<endl;
  string tar="KCPc";
  vvll dp(n,vll(5,1e18));
  dp[0][0]=0;
  using T=tuple<ll,int,int>;
  pq_small(T) que;
  que.push({0,0,0});
  if(s[0]=='K'){
    dp[0][1]=0;
    que.push({0,0,1});
  }
  while(!que.empty()){
    auto [time,pos,ok]=que.top();
    que.pop();
    if(time>dp[pos][ok])continue;
    for(auto [nxt,cst]:g[pos]){
      int nok=ok;
      if(nok<4&&tar[nok]==s[nxt])nok++;
      if(dp[nxt][nok]>time+cst){
        dp[nxt][nok]=time+cst;
        que.push({time+cst,nxt,nok});
      }
    }
  }
  ll ans=1e18;
  rep(i,0,n)ans=min(ans,dp[i][4]);
  return ans;
}

void solve(){
  int n,m;cin>>n>>m;
  vector<vector<pair<int,ll>>> g(n);
  rep(i,0,m){
    int u,v;
    ll c;
    cin>>u>>v>>c;
    u--;v--;
    g[u].emplace_back(v,c);
  }
  string s;cin>>s;
  ll ans=1e18;
  vi cs;
  rep(i,0,n){
    if(s[i]=='C')cs.emplace_back(i);
  }
  rep(t,0,20){
    for(int pos:cs){
      if(grr(0,2)==0){
        s[pos]='c';
      }
    }
    ans=min(ans,work(n,g,s));
    for(int pos:cs){
      s[pos]='C';
    }
  }
  if(ans==1e18)ans=-1;
  cout<<ans<<endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}
0