AtCoder Beginner Contest 291F - 競技プログラミング日記

ABC291F

グラフの形が特殊なことを用いる．各頂点から出ている辺の本数は，高々 $M \leq 10$ 本．

頂点 $k \in N$ を通らない $0$ から $N-1$ への path は， $$ 0 \rightarrow x \rightarrow y \rightarrow N-1 $$ の形．ここで，$x \rightarrow y$ は，$k$ を跨ぐ辺．つまり，$x < k < y$ を満たす．

実装:
$y \rightarrow N-1$ は，辺を逆向きにしたグラフにおいて $N-1 \rightarrow y$ の path を考えればよい．
前計算は，BFS で始点を$0$ の場合と $N-1$ の場合を求めておく．

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

int main() {
  auto bfs = [&](const vvll& to, ll src) -> vll {
    ll n = to.size();
    vll dis(n, INFL);
    vector<bool> vis(n);

    queue<ll> que;

    auto push = [&](ll v, ll d) -> void {
      if(vis[v]) return;
      vis[v] = true;
      que.push(v);
      dis[v] = d;
    };

    push(src, 0);
    while(que.size()){
      ll cu = que.front(); que.pop();
      ll d = dis[cu];

      for(auto ne: to[cu]){
        push(ne, d + 1);
      }
    }

    return dis;
  };

  ll n,y;
  cin >> n >> y;
  vector<string> s(n);
  cinv(s);

  vvll to(n), from(n);
  vector<vector<pll>> v(n);
  rep(i,n){
    rep(j,y) if(j+1 < n){
      if(s[i][j] == '1'){
        ll b = i+j+1; // rem: i+
        to[i].push_back(b);
        from[b].push_back(i);

        srep(k,i+1,b){
          v[k].emplace_back(i,b);
        }
      }
    }
  }


  vll d0 = bfs(to, 0);
  vll d1 = bfs(from, n-1);
  
  srep(k,1,n-1){
    ll ans = INFL;

    for(auto [a,b]: v[k]){
      ll t = 1; 
      t += d0[a];
      t += d1[b];
      chmin(ans, t);
    }
    if(ans >= INFL) ans = -1;
    cout << ans << " ";
  }

  return 0;
}