結果
| 問題 | No.3561 Collect KCPC |
| コンテスト | |
| ユーザー |
 ponjuice
|
| 提出日時 | 2026-05-29 20:37:24 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,977 bytes |
| 記録 | |
| コンパイル時間 | 3,562 ms |
| コンパイル使用メモリ | 351,856 KB |
| 実行使用メモリ | 44,152 KB |
| 最終ジャッジ日時 | 2026-05-29 20:37:37 |
| 合計ジャッジ時間 | 10,926 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_1 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点1 | 10 % | AC * 14 WA * 1 |
| 部分点2 | 20 % | AC * 13 WA * 2 |
| 部分点3 | 20 % | AC * 13 |
| 部分点4 | 50 % | AC * 47 WA * 4 |
| 合計 | 20 点 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//高速化
struct ponjuice{ponjuice(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);}}PonJuice;
//#define endl '\n' //インタラクティブ問題の時は消す
//型
using ll = long long;
using ld = long double;
template<class T>using vc = vector<T>; template<class T>using vvc = vc<vc<T>>; template<class T>using vvvc = vvc<vc<T>>;
using vi = vc<int>; using vvi = vvc<int>; using vvvi = vvvc<int>;
using vl = vc<ll>; using vvl = vvc<ll>; using vvvl = vvvc<ll>;
using pi = pair<int, int>; using pl = pair<ll, ll>;
using ull = unsigned ll;
template<class T>using priq = priority_queue<T>;
template<class T>using priqg = priority_queue<T, vc<T>, greater<T>>;
// for文
#define overload4(a, b, c, d, e, ...) e
#define rep1(n) for(ll i = 0; i < n; i++)
#define rep2(i, n) for(ll i = 0; i < n; i++)
#define rep3(i, a, b) for(ll i = a; i < b; i++)
#define rep4(i, a, b, step) for(ll i = a; i < b; i+= step)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(n) for(ll i = n-1; i >= 0; i--)
#define per2(i, n) for(ll i = n-1; i >= 0; i--)
#define per3(i, a, b) for(ll i = b-1; i >= a; i--)
#define per4(i, a, b, step) for(ll i = b-1; i >= a; i-= step)
#define per(...) overload4(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)
//関数
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define si(x) (ll)(x).size()
template<class S, class T>inline bool chmax(S& a, T b){return a < b && ( a = b , true);}
template<class S, class T>inline bool chmin(S& a, T b){return a > b && ( a = b , true);}
inline void yes(){cout << "Yes\n";}
inline void no(){cout << "No\n";}
inline void yesno(bool y = true){if(y)yes();else no();}
//定数
constexpr ll mod = 998244353;
constexpr ll minf=-(1<<29);
constexpr ll inf=(1<<29);
constexpr ll MINF=-(1LL<<60);
constexpr ll INF=(1LL<<60);
const int dx[4] ={-1, 0, 1, 0};
const int dy[4] ={ 0, 1, 0,-1};
const int dx8[8] ={-1,-1,-1, 0, 1, 1, 1, 0};
const int dy8[8] ={-1, 0, 1, 1, 1, 0,-1,-1};
void solve();
int main() {
int t = 1;
// cin >>t;
while(t--)solve();
}
void solve(){
ll n,m;
cin >> n >> m;
vector<vector<array<ll,2>>> g(n);
rep(i,0,m) {
ll u,v,c;
cin >> u >> v >> c;
u--,v--;
g[u].push_back({v, c});
}
string s;
cin >> s;
vector dist(n, vector(4, vector<array<ll,2>>(2, {INF, -1})));
using S = array<ll,4>;
priority_queue<S,vector<S>,greater<S>> q;
q.push({0, 0, 0, 0});
dist[0][0][0] = {0, -1};
string st = "KCPC";
ll ans = INF;
while(q.size()) {
auto [cst, nw, p, c] = q.top();
q.pop();
if(dist[nw][p][c][0] != cst)continue;
// cout << cst << " " << nw << " " << p << " " << c << endl;
if(st[p] == s[nw]) {
if(p == 3) {
if(dist[nw][p][c][1] != nw) chmin(ans, cst);
}
else {
if(p == 1) {
if(dist[nw][p+1][0][1] == nw) {
if(chmin(dist[nw][p+1][0], array<ll,2>{cst, nw})){
q.push({cst, nw, p+1, 0});
}
}
else if(dist[nw][p+1][1][1] == nw) {
if(chmin(dist[nw][p+1][1], array<ll,2>{cst, nw})){
q.push({cst, nw, p+1, 1});
}
}
else if(dist[nw][p+1][0][0] < dist[nw][p+1][0][1]) {
if(chmin(dist[nw][p+1][0], array<ll,2>{cst, nw})){
q.push({cst, nw, p+1, 0});
}
}else {
if(chmin(dist[nw][p+1][1], array<ll,2>{cst, nw})){
q.push({cst, nw, p+1, 1});
}
}
}
else {
if(dist[nw][p+1][0][1] == dist[nw][p][c][1]) {
if(chmin(dist[nw][p+1][0], array<ll,2>{cst, dist[nw][p][c][1]})){
q.push({cst, nw, p+1, 0});
}
}
else if(dist[nw][p+1][1][1] == dist[nw][p][c][1]) {
if(chmin(dist[nw][p+1][1], array<ll,2>{cst, dist[nw][p][c][1]})){
q.push({cst, nw, p+1, 1});
}
}
else if(dist[nw][p+1][0][0] < dist[nw][p+1][0][1]) {
if(chmin(dist[nw][p+1][0], array<ll,2>{cst, dist[nw][p][c][1]})){
q.push({cst, nw, p+1, 0});
}
}else {
if(chmin(dist[nw][p+1][1], array<ll,2>{cst, dist[nw][p][c][1]})){
q.push({cst, nw, p+1, 1});
}
}
}
}
}
for(auto [to, cost]: g[nw]) {
if(dist[to][p][0][1] == dist[nw][p][c][1]) {
if(chmin(dist[to][p][0], array<ll,2>{cst+cost, dist[nw][p][c][1]})){
q.push({cst+cost, to, p, 0});
}
}
else if(dist[to][p][1][1] == dist[nw][p][c][1]) {
if(chmin(dist[to][p][1], array<ll,2>{cst+cost, dist[nw][p][c][1]})){
q.push({cst+cost, to, p, 1});
}
}
else if(dist[to][p][0][0] < dist[to][p][0][1]) {
if(chmin(dist[to][p][0], array<ll,2>{cst+cost, dist[nw][p][c][1]})){
q.push({cst+cost, to, p, 0});
}
}else {
if(chmin(dist[to][p][1], array<ll,2>{cst+cost, dist[nw][p][c][1]})){
q.push({cst+cost, to, p, 1});
}
}
}
}
cout << (ans==INF?-1:ans) << endl;
}