Submission #70542863

---

Source Code Expand

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

// BFS（2つめのスタート地点まで記録するように改造した版）
void bfs(const vector<vector<int>>& graph, vector<int>& distances1, vector<int>& distances2, const vector<int>& start) {

  // BFS用のqueue（のつもりのdeque）
  // 「頂点、距離、スタート」の候補
  deque<tuple<int,int,int>> que;

  // スタート地点候補（安全地帯）を全部距離0で候補に入れる
  for (int v : start) {
    que.emplace_back(v,0,v);
  }

  // 各頂点から最寄りのスタート地点
  vector<int> roots(graph.size(),-1);

  // BFSのループを実行
  while (!que.empty()) {

    // 先頭を取り出す
    auto [v,d,r] = que.front();
    que.pop_front();

    // 最寄りのスタート地点と同じ情報だったら破棄
    if (roots.at(v)==r) continue;

    // 最寄り情報がなかったら、最寄り情報に入れる
    if (distances1.at(v)==-1) {
      distances1.at(v) = d;
      roots.at(v) = r;
    }

    // 最寄り情報があるが次点情報がなかったら、次点情報に入れる
    else if (distances2.at(v)==-1) {
      distances2.at(v) = d;
    }

    // どちらでもなければ、破棄
    else continue;

    // 有効な情報だったら、隣接頂点をqueueに入れる
    // （この時点で次点情報をチェックしてもいいが、
    //   しなくても間に合うし、コードがややこしくなるので、やらないことにする）
    for (int next : graph.at(v)) {
      que.emplace_back(next,d+1,r);
    }

  }
}

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, m;
  cin >> n >> m;

  // 0始まりに直して、隣接リストに受け取る
  vector<int> u(m), v(m);
  vector<vector<int>> graph(n);
  for (int i=0; i<m; i++) {
    cin >> u.at(i) >> v.at(i);
    u.at(i)--;
    v.at(i)--;
    graph.at(u.at(i)).emplace_back(v.at(i));
    graph.at(v.at(i)).emplace_back(u.at(i));
  }

  string s;
  cin >> s;

  //////////////// 出力変数定義 ////////////////

  vector<int> result;
  result.reserve(n);

  //////////////////// 処理 ////////////////////

  // 最寄りと次点までの距離情報
  vector<int> distances1(n,-1);
  vector<int> distances2(n,-1);

  // スタート地点（安全地帯）情報
  vector<int> start;
  for (int i=0; i<n; i++) {
    if (s.at(i)=='S') start.emplace_back(i);
  }

  // BFSをする
  bfs(graph,distances1,distances2,start);

  // 危険地帯について、順番に、出力する値を求めていく
  for (int i=0; i<n; i++) {
    if (s.at(i)=='D') result.emplace_back(distances1.at(i)+distances2.at(i));
  }

  //////////////////// 出力 ////////////////////

  for (size_t i=0; i<result.size(); i++) {
    cout << result.at(i) << endl;
  }

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result