Dial 01

Code

#include <vector>
#include <queue>
using i64 = long long;

/*
 * delta(V v, fn (V t, i64 weight))
 * index(V v) -> int
 */
template<class V, class W, class Delta, class Index>
std::vector<i64> dial01(std::size_t N, W inf, V s, Delta delta, Index index) {
  std::vector<i64> dist(N, inf);
  using P = std::pair<V, W>;
  std::deque<P> que;
  dist[index(s)] = 0;
  que.push_back({ s, dist[index(s)]});
  while(!que.empty()) {
    V v = que.front().first;
    W d = que.front().second;
    que.pop_front();
    if(dist[index(v)] < d) continue;
    delta(v, [&](V t, i64 weight) {
        if(dist[index(t)] > dist[index(v)] + weight) {
          dist[index(t)] = dist[index(v)] + weight;
          if(weight == 0) que.push_front({ t, dist[index(t)] });
          else que.push_back({ t, dist[index(t)] });
        }
    });
  }
  return dist;
}