comp-library

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

View the Project on GitHub luzhiled1333/comp-library

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

Depends on

Code

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

#include "src/graph/class/dynamic-graph.hpp"

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

#include <iostream>

namespace luz {

  void main_() {
    usize v = input(), e = input(), source = input();

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

    graph g(v);
    for ([[maybe_unused]] usize _: rep(0, e)) {
      usize s = input(), t = input();
      u32 d = input();
      g.add_directed_edge(s, t, d);
    }

    sssp::InNonNegativeWeightedGraph solver(g, source);
    auto dists = solver.get_distances();
    for (auto &dist: dists) {
      if (dist == solver.inf()) {
        std::cout << "INF" << std::endl;
      } else {
        std::cout << dist << std::endl;
      }
    }
  }

} // namespace luz

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

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

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

#include <cstddef>

namespace luz {

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

} // namespace luz
#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) {
      assert(from < size());
      assert(to < size());
      g[from].emplace_back(from, to, cost, edge_count++);
    }

    void add_undirected_edge(usize u, usize v, cost_type cost = 1) {
      assert(u < size());
      assert(v < size());
      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 4 "test/aoj/grl_1_a/dynamic-graph.test.cpp"

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

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

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 4 "src/cpp-template/header/input.hpp"

#include <iostream>

namespace luz {

  template < typename T = i64 >
  T input() {
    T tmp;
    std::cin >> tmp;
    return tmp;
  }

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

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

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

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

namespace luz {

  template < typename T >
  class Edge {
   public:
    using cost_type = T;

    usize from, to;
    T cost;
    usize id;
    Edge() = default;
    Edge(usize from_, usize to_, T cost_, usize id_)
        : from(from_),
          to(to_),
          cost(cost_),
          id(id_) {}
  };

  template < typename T >
  using Edges = std::vector< Edge< T > >;

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

#line 2 "src/cpp-template/header/change-min.hpp"

namespace luz {

  template < typename T1, typename T2 >
  inline bool chmin(T1 &a, T2 b) {
    return a > b and (a = b, true);
  }

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

#include <functional>
#include <limits>
#include <queue>
#include <utility>
#line 11 "src/graph/single-source-shortest-path/in-non-negative-weighted-graph.hpp"

namespace luz::sssp {

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

    static constexpr usize undefined_ =
        std::numeric_limits< usize >::max();
    static constexpr cost_type inf_ =
        std::numeric_limits< cost_type >::max();

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

    void dijkstra(usize s) {
      using pq_type = std::pair< cost_type, usize >;
      std::priority_queue< pq_type, std::vector< pq_type >,
                           std::greater< pq_type > >
          pq;

      ds[s] = 0;
      pq.emplace(ds[s], s);

      while (not pq.empty()) {
        auto [cost, v] = pq.top();
        pq.pop();

        if (ds[v] < cost) continue;
        for (auto &e: g[v]) {
          if (chmin(ds[e.to], cost + e.cost)) {
            pq.emplace(ds[e.to], e.to);
            parents[e.to] = v;
            ids[e.to]     = e.id;
          }
        }
      }
    }

   public:
    explicit InNonNegativeWeightedGraph(const graph &g_, usize source)
        : g(g_),
          g_size(g.size()),
          ds(g_size, inf_),
          parents(g_size, undefined_),
          ids(g_size, undefined_) {
      dijkstra(source);
    }

    inline graph get_original_graph() const {
      return g;
    }

    static inline cost_type inf() {
      return inf_;
    }

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

    inline std::vector< cost_type > get_distances() const {
      return ds;
    }

    static inline usize undefined() {
      return undefined_;
    }

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

    inline std::vector< usize > get_parents() const {
      return parents;
    }

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

    inline std::vector< usize > get_edge_labels() const {
      return ids;
    }
  };

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

#line 13 "test/aoj/grl_1_a/dynamic-graph.test.cpp"

namespace luz {

  void main_() {
    usize v = input(), e = input(), source = input();

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

    graph g(v);
    for ([[maybe_unused]] usize _: rep(0, e)) {
      usize s = input(), t = input();
      u32 d = input();
      g.add_directed_edge(s, t, d);
    }

    sssp::InNonNegativeWeightedGraph solver(g, source);
    auto dists = solver.get_distances();
    for (auto &dist: dists) {
      if (dist == solver.inf()) {
        std::cout << "INF" << std::endl;
      } else {
        std::cout << dist << std::endl;
      }
    }
  }

} // namespace luz

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