提出 #41205263

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int N, M;

void dijkstra(int st, const vector<vector<int>> &es, vector<ll> &ds)
{
  fill(ds.begin(), ds.end(), INF);

  priority_queue<
    pair<ll, int>,
    vector<pair<ll, int>>,
    greater<pair<ll, int>>> que;

  ds[st] = 0;
  que.push(make_pair(0, st));

  while(!que.empty()){
    auto [d, i] = que.top(); que.pop();

    if (d > ds[i]) continue;

    for (int j : es[i]){
      if (chmin(ds[j], ds[i] + 1)){
	que.push(make_pair(ds[i] + 1, j));
      }
    }
  }
}
    
vector<ll> dist, distr;
vector<vector<int>> edges, edgesr;

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  // Input
  cin >> N >> M;
  vector<string> s(N);
  for (auto &t : s) cin >> t;

  // Dijkstra from 0 and N-1
  dist.resize(N);
  distr.resize(N);
  edges.resize(N);
  edgesr.resize(N);

  for (int i = 0; i < N - 1; i++){
    for (int j = 0; j < M; j++){
      if (i + j + 1 < N && s[i][j] == '1'){
	edges[i].push_back(i + j + 1);
	edgesr[i + j + 1].push_back(i);
      }
    }
  }
  
  dijkstra(0, edges, dist);
  dijkstra(N-1, edgesr, distr);

  // Solve and Output
  for (int i = 1; i < N - 1; i++){
    ll ans = INF;
    for (int j = i - 1 - M; j < i; j++){
      if (j >= 0){
	for (int k : edges[j]){
	  if (k > i){
	    chmin(ans, dist[j] + distr[k] + 1);
	  }
	}
      }
    }

    if (ans == INF) cout << -1 << " ";
    else cout << ans << " ";
  }

  cout << endl;
  return 0;
}

提出情報

ジャッジ結果