提出 #25464575

---

ソースコード 拡げる

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

template <typename CostType>
struct Edge {
  int src, dst; CostType cost;
  Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {}
  inline bool operator<(const Edge &x) const {
    return cost != x.cost ? cost < x.cost : dst != x.dst ? dst < x.dst : src < x.src;
  }
  inline bool operator<=(const Edge &x) const { return !(x < *this); }
  inline bool operator>(const Edge &x) const { return x < *this; }
  inline bool operator>=(const Edge &x) const { return !(*this < x); }
};

template <typename CostType>
struct Dijkstra {
  const CostType inf;

  Dijkstra(const std::vector<std::vector<Edge<CostType>>> &graph,
           const CostType inf = std::numeric_limits<CostType>::max())
  : graph(graph), inf(inf) {}

  std::vector<CostType> build(int s) {
    is_built = true;
    int n = graph.size();
    std::vector<CostType> dist(n, inf);
    dist[s] = 0;
    prev.assign(n, -1);
    using Pci = std::pair<CostType, int>;
    std::priority_queue<Pci, std::vector<Pci>, std::greater<Pci>> que;
    que.emplace(0, s);
    while (!que.empty()) {
      CostType cost; int ver; std::tie(cost, ver) = que.top(); que.pop();
      if (dist[ver] < cost) continue;
      for (const Edge<CostType> &e : graph[ver]) {
        if (dist[e.dst] > dist[ver] + e.cost) {
          dist[e.dst] = dist[ver] + e.cost;
          prev[e.dst] = ver;
          que.emplace(dist[e.dst], e.dst);
        }
      }
    }
    return dist;
  }

  std::vector<int> build_path(int t) const {
    assert(is_built);
    std::vector<int> res;
    for (; t != -1; t = prev[t]) res.emplace_back(t);
    std::reverse(res.begin(), res.end());
    return res;
  }

private:
  bool is_built = false;
  std::vector<std::vector<Edge<CostType>>> graph;
  std::vector<int> prev;
};

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<Edge<int>>> graph(n + 1);
  for (int i = 1; i <= n; ++i) {
    graph[i].emplace_back(i, i - 1, 0);
    graph[i - 1].emplace_back(i - 1, i, 1);
  }
  while (m--) {
    int l, r, x;
    std::cin >> l >> r >> x;
    graph[l - 1].emplace_back(l - 1, r, r - l + 1 - x);
  }
  std::vector<int> a = Dijkstra(graph).build(0);
  for (int i = 1; i <= n; ++i) {
    std::cout << 1 - (a[i] - a[i - 1]) << " \n"[i == n];
  }
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In instantiation of ‘Dijkstra<CostType>::Dijkstra(const std::vector<std::vector<Edge<CostType> > >&, CostType) [with CostType = int]’:
./Main.cpp:81:38:   required from here
./Main.cpp:64:44: warning: ‘Dijkstra<int>::graph’ will be initialized after [-Wreorder]
   64 |   std::vector<std::vector<Edge<CostType>>> graph;
      |                                            ^~~~~
./Main.cpp:25:18: warning:   ‘const int Dijkstra<int>::inf’ [-Wreorder]
   25 |   const CostType inf;
      |                  ^~~
./Main.cpp:27:3: warning:   when initialized here [-Wreorder]
   27 |   Dijkstra(const std::vector<std::vector<Edge<CostType>>> &graph,
      |   ^~~~~~~~

ジャッジ結果