AtCoder Beginner Contest 429E問題

ABC429E

解法

多始点BFS. イメージとしては，始点とpath に色を付けて区別しながら BFS.

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n,m;

  cin >> n >> m;

  vvll to(n);

  rep(i,m){

    ll a,b; cin >> a >> b;

    --a, --b;

    to[a].push_back(b);

    to[b].push_back(a);

  }

  string s; cin >> s;

  using T = tuple<ll,ll,ll>; // <dist, vtx, source vtx>

  queue<T> que;

  vector<vector<pll>> dist(n); // <dist, source vtx>

  auto push = [&](ll d, ll v, ll sv) -> void {

    if(dist[v].size() >= 2) return;

    for(auto p: dist[v]) if(p.second == sv) return;

   

    que.push({d, v, sv});

    dist[v].push_back({d, sv});

  };

 

  rep(v,n) if(s[v] == 'S') push(0, v, v);

  while(que.size()){

    auto [d, v, sv] = que.front(); que.pop();

    for(auto nv: to[v]){

      push(d+1, nv, sv);

    }

  }

  rep(v,n) if(s[v] == 'D'){

    assert(dist[v].size() == 2);

    ll ans = dist[v][0].first + dist[v][1].first;

    cout << ans << '\n';

  }

  return 0;

}