retrograde_weighted.cpp

#include "definition.cpp"
#include "game.cpp"

template <typename Cost> struct Game_with_Cost {
  Game win;
  Cost cost;
  Game_with_Cost() : win(DRAW), cost(inf<Cost>()) { ; }
  Game_with_Cost(Game w, Cost c) : win(w), cost(c) { ; }
};

template <typename edge_t, typename Cost = typename edge_t::cost_type>
std::vector<Game_with_Cost<Cost>> retrograde(const graph_t<edge_t> &g) {
  using P = std::pair<Cost, int>;
  const int n = g.size();
  std::vector<std::vector<P>> rg(n);
  for (int i = 0; i < n; ++i) {
    for (const auto &e : g[i]) rg[e.to].emplace_back(e.cost, i);
  }
  std::vector<int> cnt(n);
  for (int i = 0; i < n; ++i) cnt[i] = g[i].size();
  std::priority_queue<P, std::vector<P>, std::greater<P>> que;
  std::vector<Game_with_Cost<Cost>> res(n);
  for (int i = 0; i < n; ++i) {
    if (cnt[i] == 0) {
      res[i] = Game_with_Cost<Cost>(LOSE, 0);
      que.emplace(Cost(0), i);
    }
  }
  while (!que.empty()) {
    Cost cost;
    int v;
    std::tie(cost, v) = que.top();
    que.pop();
    if (res[v].win == WIN) {
      if (res[v].cost != cost) continue;
      for (const P &e : rg[v]) {
        if (res[e.second].win == WIN) continue;
        cnt[e.second]--;
        if (cnt[e.second] == 0) {
          res[e.second].win = LOSE;
          que.emplace(Cost(0), e.second);
        }
      }
    }
    else {
      for (const edge_t &e : g[v]) {
        cost = std::max(cost, res[e.to].cost + e.cost);
      }
      res[v].cost = cost;
      for (const P &e : rg[v]) {
        res[e.second].win = WIN;
        if (cost + e.first < res[e.second].cost) {
          res[e.second].cost = cost + e.first;
          que.emplace(res[e.second].cost, e.second);
        }
      }
    }
  }
  return res;
}