#1168676 (C++17) No.3561 Collect KCPC

• 問題: No.3561 Collect KCPC
• ユーザー: tnakao0123
• 提出日時: 2026-06-08 19:47:14
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,102 bytes
• コンパイル時間: 869 ms
• コンパイル使用メモリ: 81,840 KB
• 実行使用メモリ: 43,180 KB
• 最終ジャッジ日時: 2026-06-08 19:47:24
• 合計ジャッジ時間: 9,061 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

サブタスク	配点	結果
部分点1	10 %	AC * 11 WA * 4
部分点2	20 %	AC * 12 WA * 3
部分点3	20 %	AC * 13
部分点4	50 %	AC * 39 WA * 12
合計	20 点

ソースコード

/* -*- coding: utf-8 -*-
 *
 * 3561.cc:  No.3561 Collect KCPC - yukicoder
 */

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 100000;
const int K = 4;
const int MAX_GN = MAX_N * K;
const long long LINF = 1LL << 60;

/* typedef */

using ll = long long;
using pii = pair<int,int>;
using vpii = vector<pii>;

struct Dist {
  ll d0, d1;
  int u0, u1;
  Dist(): d0(LINF), u0(-1), d1(LINF), u1(-1) {}
  Dist(ll _d0, int _u0, ll _d1, int _u1): d0(_d0), u0(_u0), d1(_d1), u1(_u1) {}

  Dist operator+(const int w) { return Dist(d0 + w, u0, d1 + w, u1); }
  Dist operator+(const Dist t) {
    ll rd0, rd1;
    int ru0, ru1;
    if (d0 <= t.d0) {
      rd0 = d0, ru0 = u0;
      if (d1 <= t.d0 || ru0 == t.u0) rd1 = d1, ru1 = u1;
      else rd1 = t.d0, ru1 = t.u0;
    }
    else { // d0 > t.d0
      rd0 = t.d0, ru0 = t.u0;
      if (t.d1 <= d0 || ru0 == u0) rd1 = t.d1, ru1 = t.u1;
      else rd1 = d0, ru1 = u0;
    }
    return Dist(rd0, ru0, rd1, ru1);
  }

  bool operator<(const Dist t) const {
    return d0 < t.d0 || (d0 == t.d0 && d1 < t.d1);
  }
  bool operator>(const Dist t) const {
    return d0 > t.d0 || (d0 == t.d0 && d1 > t.d1);
  }
  bool operator==(const Dist t) const {
    return d0 == t.d0 && d1 == t.d1;
  }
  bool operator!=(const Dist t) const {
    return d0 != t.d0 || d1 != t.d1;
  }

  void print() const {
    printf(" Dist(%lld,%d,%lld,%d)\n", d0, u0, d1, u1);
  }
};

using pdi = pair<Dist,int>;

/* global variables */

vpii nbrs[MAX_N], rnbrs[MAX_N];
char s[MAX_N + 4];
int fs[MAX_N];
Dist ds0[MAX_GN], ds1[MAX_GN];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u--, v--;
    nbrs[u].push_back({v, w});
    rnbrs[v].push_back({u, w});
  }
  scanf("%s", s);

  for (int i = 0; i < n; i++)
    fs[i] = (s[i] == 'K') ? 1 : (s[i] == 'C') ? 2 : (s[i] == 'P') ? 3 : 0;

  int gn = (n << 2);
  fill(ds0, ds0 + gn, Dist());
  ds0[0] = Dist(0, 0, LINF, -1);
  priority_queue<pdi,vector<pdi>,greater<pdi>> q0;
  q0.push({ds0[0], 0});

  while (! q0.empty()) {
    auto [ud, u] = q0.top(); q0.pop();
    if (ud != ds0[u]) continue;

    int up = (u >> 2), uf = (u & 3);
    //printf(" %d,%d:", up, uf); ud.print();
    if (uf >= 3) continue;

    if (fs[up] == uf + 1) {
      int v = (up << 2) | (uf + 1);
      auto vd = (uf == 1) ? Dist(ud.d0, up, LINF, -1) : ud;
      if (ds0[v] > vd) {
	ds0[v] = ds0[v] + vd;
	q0.push({ds0[v], v});
      }
    }

    for (auto [vp, w]: nbrs[up]) {
      int v = (vp << 2) | uf;
      auto vd = ud + w;
      //printf("  %d,%d:", vp, uf); vd.print();
      if (ds0[v] > vd) {
	ds0[v] = ds0[v] + vd;
	//printf("  ds0[%d]=", v); ds0[v].print();
	q0.push({ds0[v], v});
      }
    }
  }
  //for (int i = 0; i < n; i++)
  //  if (fs[i] == 3) printf(" %d:", i), ds0[(i << 2) | 3].print();

  fill(ds1, ds1 + gn, Dist());
  priority_queue<pdi,vector<pdi>,greater<pdi>> q1;
  for (int i = 0; i < n; i++)
    if (fs[i] == 2) {
      int u = (i << 2) | 2;
      ds1[u] = Dist(0, i, LINF, -1);
      q1.push({ds1[u], u});
    }

  while (! q1.empty()) {
    auto [ud, u] = q1.top(); q1.pop();
    if (ds1[u] != ud) continue;

    int up = (u >> 2), uf = (u & 3);
    //printf(" %d,%d:", up, uf); ud.print();
    if (uf >= 3) continue;

    for (auto [vp, w]: rnbrs[up]) {
      int v = (vp << 2) | uf;
      auto vd = ud + w;
      if (ds1[v] > vd) {
	ds1[v] = ds1[v] + vd;
	q1.push({ds1[v], v});
      }
    }
  }

  ll mind = LINF;
  for (int i = 0; i < n; i++)
    if (fs[i] == 3) {
      int u0 = (i << 2) | 3, u1 = (i << 2) | 2;
      auto &ud0 = ds0[u0], &ud1 = ds1[u1];
      //ud0.print(); ud1.print();

      if (ud0.u0 != ud1.u0) mind = min(mind, ud0.d0 + ud1.d0);
      if (ud0.u0 != ud1.u1) mind = min(mind, ud0.d0 + ud1.d1);
      if (ud0.u1 != ud1.u0) mind = min(mind, ud0.d1 + ud1.d0);
      if (ud0.u1 != ud1.u1) mind = min(mind, ud0.d1 + ud1.d1);
    }

  printf("%lld\n", (mind < LINF) ? mind : -1LL);
  
  return 0;
}