syakyo-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Luzhiled/syakyo-library

:heavy_check_mark: test/aoj/grl_1_b/dynamic-graph.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/graph/class/edge/edge.hpp"
#include "src/graph/class/dynamic-graph.hpp"
#include "src/graph/single-source-shortest-path/in-weighted-graph.hpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n, m, source;
    std::cin >> n >> m >> source;

    using edge  = Edge< i32 >;
    using graph = DynamicGraph< edge >;

    graph g(n);
    while (m--) {
      usize s, t;
      i32 d;

      std::cin >> s >> t >> d;
      g.add_directed_edge(s, t, d);
    }

    sssp::InWeightedGraph< graph > solver(g, source);
    for (usize v = 0; v < n; v++) {
      if (solver.distance(v) == solver.negative_inf) {
        std::cout << "NEGATIVE CYCLE" << std::endl;
        return;
      }
    }

    for (usize v = 0; v < n; v++) {
      if (solver.distance(v) == solver.inf) {
        std::cout << "INF" << std::endl;
      } else {
        std::cout << solver.distance(v) << std::endl;
      }
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "test/aoj/grl_1_b/dynamic-graph.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32 = std::int32_t;
  using i64 = std::int64_t;
  using u32 = std::uint32_t;
  using u64 = std::uint64_t;

}
#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

}
#line 2 "src/graph/class/edge/edge.hpp"

#line 4 "src/graph/class/edge/edge.hpp"

namespace luz {

  template < typename T >
  struct Edge {
    using cost_type = T;

    usize from, to;
    T cost;
    usize id;

    Edge() = default;
    
    Edge(usize f, usize t, T c, usize i) : from(f), to(t), cost(c), id(i) {}
  };

} // namespace luz
#line 2 "src/graph/class/dynamic-graph.hpp"

#line 4 "src/graph/class/dynamic-graph.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename Edge >
  class DynamicGraph {

    using Edges = std::vector< Edge >;

   protected:
    std::vector< Edges > g;
    usize edge_count;

   public:
    using cost_type = typename Edge::cost_type;

    DynamicGraph() = default;
    explicit DynamicGraph(usize n): g(n), edge_count(0) {}

    usize size() const {
      return g.size();
    }

    void add_directed_edge(usize from, usize to, cost_type cost = 1) {
      g[from].emplace_back(from, to, cost, edge_count++);
    }

    void add_undirected_edge(usize u, usize v, cost_type cost = 1) {
      assert(u != v);
      g[u].emplace_back(u, v, cost, edge_count);
      g[v].emplace_back(v, u, cost, edge_count++);
    }

    Edges operator[](const usize &v) {
      return g[v];
    }

    const Edges operator[](const usize &v) const {
      return g[v];
    }

  };

} // namespace luz
#line 2 "src/graph/single-source-shortest-path/in-weighted-graph.hpp"

#line 4 "src/graph/single-source-shortest-path/in-weighted-graph.hpp"

#include <limits>
#include <queue>
#line 8 "src/graph/single-source-shortest-path/in-weighted-graph.hpp"

namespace luz::sssp {

  template < class G >
  class InWeightedGraph {
    using cost_type = typename G::cost_type;
    using graph     = G;

    graph g;
    usize n;

    std::vector< cost_type > ds;
    std::vector< usize > parents, ids;

    // O(nm)
    void spfa(usize s) {
      std::queue< usize > que;
      std::vector< usize > ds_update_cnt(n);
      std::vector< bool > in_que(n);

      ds[s]            = 0;
      in_que[s]        = true;
      ds_update_cnt[s] = 0;
      que.emplace(s);

      while (not que.empty()) {
        usize v = que.front();
        que.pop();
        in_que[v] = false;

        for (const auto &e: g[v]) {
          usize u        = e.to;
          cost_type cost = e.cost;
          if (ds[v] + cost >= ds[u]) {
            continue;
          }

          ds[u]      = ds[v] + cost;
          parents[u] = v;
          ids[u]     = e.id;

          if (in_que[u]) {
            continue;
          }

          in_que[u] = true;
          ds_update_cnt[u]++;

          if (ds_update_cnt[u] < 2 * n) {
            que.emplace(u);
          }
        }
      }

      for (usize v = 0; v < n; v++) {
        if (ds_update_cnt[v] >= n) {
          ds[v]      = negative_inf;
          parents[v] = undefined;
          ids[v]     = undefined;
        }
      }
    }

   public:
    static constexpr cost_type inf = std::numeric_limits< cost_type >::max();
    static constexpr cost_type negative_inf = std::numeric_limits< cost_type >::min();
    static constexpr usize undefined = std::numeric_limits< usize >::max();

    explicit InWeightedGraph(const graph &g, usize s)
        : g(g),
          n(g.size()),
          ds(n, inf),
          parents(n, undefined),
          ids(n, undefined) {
      spfa(s);
    }

    inline cost_type distance(const usize v) const {
      return ds[v];
    }

    inline usize parent(const usize v) const {
      return parents[v];
    }

    inline usize edge_label(const usize v) const {
      return ids[v];
    }

  };

} // namespace luz::sssp
#line 8 "test/aoj/grl_1_b/dynamic-graph.test.cpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n, m, source;
    std::cin >> n >> m >> source;

    using edge  = Edge< i32 >;
    using graph = DynamicGraph< edge >;

    graph g(n);
    while (m--) {
      usize s, t;
      i32 d;

      std::cin >> s >> t >> d;
      g.add_directed_edge(s, t, d);
    }

    sssp::InWeightedGraph< graph > solver(g, source);
    for (usize v = 0; v < n; v++) {
      if (solver.distance(v) == solver.negative_inf) {
        std::cout << "NEGATIVE CYCLE" << std::endl;
        return;
      }
    }

    for (usize v = 0; v < n; v++) {
      if (solver.distance(v) == solver.inf) {
        std::cout << "INF" << std::endl;
      } else {
        std::cout << solver.distance(v) << std::endl;
      }
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page