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

• 問題: No.3561 Collect KCPC
• ユーザー: kwm_t
• 提出日時: 2026-05-29 23:54:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 254 ms / 6,000 ms
• コード長: 3,655 bytes
• コンパイル時間: 2,924 ms
• コンパイル使用メモリ: 366,160 KB
• 実行使用メモリ: 47,024 KB
• 最終ジャッジ日時: 2026-05-29 23:54:33
• 合計ジャッジ時間: 9,290 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

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

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }

template<typename T> using pq = priority_queue<T, vector<T>, greater<T>>;
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m; cin >> n >> m;
	vector<vector<pair<int, long long>>>g(n), h(n);
	rep(i, m) {
		int u, v, c; cin >> u >> v >> c;
		u--, v--;

		g[u].emplace_back(v, c);
		h[v].emplace_back(u, c);
	}
	string s; cin >> s;
	// KC
	vector<long long>dp0;
	{
		// *,K,KC
		vector dp(3, vector<long long>(n, LINF));
		pq<pair<long long, P>> que;
		if (s[0] != 'K') {
			dp[0][0] = 0;
			que.push({ 0,{0,0 } });
		}
		else {
			dp[1][0] = 0;
			que.push({ 0,{1,0 } });
		}
		while (!que.empty()) {
			auto[dist, tmp] = que.top();
			auto[t, v] = tmp;
			que.pop();
			if (dp[t][v] < dist)continue;
			for (auto[nv, d] : g[v]) {
				if (t == 0) {
					if (s[nv] == 'K') {
						// 0->1
						if (chmin(dp[t + 1][nv], dp[t][v] + d)) {
							que.push({ dp[t + 1][nv],{t + 1,nv } });
						}
					}
					else {
						// 0->0
						if (chmin(dp[t][nv], dp[t][v] + d)) {
							que.push({ dp[t][nv],{t,nv } });
						}
					}
				}
				else {
					if (s[nv] == 'C') {
						// 1->2
						if (chmin(dp[t + 1][nv], dp[t][v] + d)) {
							//que.push({ dp[t + 1][nv],{t + 1,nv } });
						}
					}
					else {
						// 1->1
						if (chmin(dp[t][nv], dp[t][v] + d)) {
							que.push({ dp[t][nv],{t,nv } });
						}
					}
				}
			}
		}
		dp0 = dp[2];
	}
	auto dijk = [&](vector<vector<pair<int, long long>>> g, vector<pair<int, long long>>st) {
		vector dp(n, vector<pair<long long, int>>(2, { LINF,-1 }));
		pq<pair<pair<long long, int>, int>> que;// dist from now
		for (auto[p, d] : st) {
			dp[p][0] = { d,p };
			que.push({ {d,p},p });
		}
		while (!que.empty()) {
			auto[p, v] = que.top();
			auto[d, f] = p;
			que.pop();
			if (dp[v][0] != p && dp[v][1] != p) continue;
			for (auto[nv, c] : g[v]) {
				pair<long long, int> np = { d + c, f };
				if (np.first < dp[nv][0].first) {
					if (np.second != dp[nv][0].second) {
						dp[nv][1] = dp[nv][0];
					}
					dp[nv][0] = np;
					que.push({ np, nv });
				}
				else if (np.first < dp[nv][1].first) {
					if (np.second != dp[nv][0].second) {
						dp[nv][1] = np;
						que.push({ np, nv });
					}
				}
			}
		}
		return dp;
	};
	vector<pair<int, long long>>st1;
	rep(i, n)if (s[i] == 'C')st1.emplace_back(i, dp0[i]);
	auto dp1 = dijk(g, st1);
	// C->P(rev)
	vector<pair<int, long long>>st2;
	rep(i, n)if (s[i] == 'C')st2.emplace_back(i, 0);
	auto dp2 = dijk(h, st2);
	long long ans = LINF;
	rep(i, n)if (s[i] == 'P') {
		rep(p, 2)rep(q, 2) {
			if (dp1[i][p].second == -1)continue;
			if (dp2[i][q].second == -1)continue;
			if (dp1[i][p].second == dp2[i][q].second)continue;
			long long val = dp1[i][p].first + dp2[i][q].first;
			chmin(ans, val);
		}
	}
	if (ans == LINF)ans = -1;
	cout << ans << endl;
	return 0;
}