tests/tsp.test.cpp

• View this file on GitHub
• Last update: 2025-01-26 15:10:23+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_A

Depends on

• Assertion macro (tools/assert_that.hpp)
• chmin function (tools/chmin.hpp)
• $2^x$ (tools/pow2.hpp)
• Traveling salesman problem (tools/tsp.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_A

#include <iostream>
#include <cassert>
#include <iterator>
#include "tools/tsp.hpp"
#include "tools/assert_that.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll V, E;
  std::cin >> V >> E;
  tools::tsp<true, ll> graph(V);
  for (ll i = 0; i < E; ++i) {
    ll s, t, d;
    std::cin >> s >> t >> d;
    graph.add_edge(s, t, d);
  }

  const auto res = graph.query();
  if (res) {
    const auto& [answer, vids, eids] = *res;
    assert_that(std::ssize(vids) == V);
    assert_that(std::ssize(eids) == V);
    ll sum = 0;
    for (ll i = 0; i < V; ++i) {
      assert_that(graph.get_edge(eids[i]).from == vids[i]);
      assert_that(graph.get_edge(eids[i]).to == vids[(i + 1) % V]);
      sum += graph.get_edge(eids[i]).cost;
    }
    assert_that(answer == sum);
    std::cout << answer << '\n';
  } else {
    std::cout << -1 << '\n';
  }

  return 0;
}

#line 1 "tests/tsp.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_A

#include <iostream>
#include <cassert>
#include <iterator>
#line 1 "tools/tsp.hpp"



#include <cstddef>
#include <vector>
#include <limits>
#line 8 "tools/tsp.hpp"
#include <utility>
#include <algorithm>
#include <optional>
#include <tuple>
#line 1 "tools/pow2.hpp"



#include <type_traits>
#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 1 "tools/chmin.hpp"



#line 6 "tools/chmin.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 14 "tools/tsp.hpp"

namespace tools {

  template <bool Directed, typename T>
  class tsp {
  public:
    struct edge {
      ::std::size_t id;
      ::std::size_t from;
      ::std::size_t to;
      T cost;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<::std::size_t>> m_graph;

  public:
    tsp() = default;
    tsp(const ::tools::tsp<Directed, T>&) = default;
    tsp(::tools::tsp<Directed, T>&&) = default;
    ~tsp() = default;
    ::tools::tsp<Directed, T>& operator=(const ::tools::tsp<Directed, T>&) = default;
    ::tools::tsp<Directed, T>& operator=(::tools::tsp<Directed, T>&&) = default;

    explicit tsp(const ::std::size_t n) : m_graph(n, ::std::vector<::std::size_t>(n, ::std::numeric_limits<::std::size_t>::max())) {
      assert(n >= 2);
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(::std::size_t u, ::std::size_t v, const T& w) {
      assert(u < this->size());
      assert(v < this->size());
      if constexpr (!Directed) {
        ::std::tie(u, v) = ::std::minmax({u, v});
      }
      this->m_edges.push_back(edge({this->m_edges.size(), u, v, w}));
      if (this->m_graph[u][v] == ::std::numeric_limits<::std::size_t>::max() || w < this->m_edges[this->m_graph[u][v]].cost) {
        this->m_graph[u][v] = this->m_edges.size() - 1;
      }
      if constexpr (!Directed) {
        if (this->m_graph[v][u] == ::std::numeric_limits<::std::size_t>::max() || w < this->m_edges[this->m_graph[v][u]].cost) {
          this->m_graph[v][u] = this->m_edges.size() - 1;
        }
      }
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const ::std::size_t k) const {
      assert(k < this->m_edges.size());
      return this->m_edges[k];
    }

    const ::std::vector<edge>& edges() const {
      return this->m_edges;
    }

    ::std::optional<::std::tuple<T, ::std::vector<::std::size_t>, ::std::vector<::std::size_t>>> query() const {
      auto dp = ::std::vector(::tools::pow2(this->size()), ::std::vector(this->size(), ::std::numeric_limits<T>::max()));
      dp[0][0] = 0;
      for (::std::size_t state = 1; state < ::tools::pow2(this->size()); ++state) {
        for (::std::size_t v = 0; v < this->size(); ++v) {
          if ((static_cast<::std::size_t>(1) << v) & state) {
            const auto prev_state = state & ~(static_cast<::std::size_t>(1) << v);
            for (::std::size_t u = 0; u < this->size(); ++u) {
              if (this->m_graph[u][v] < ::std::numeric_limits<::std::size_t>::max()) {
                if (dp[prev_state][u] < ::std::numeric_limits<T>::max()) {
                  ::tools::chmin(dp[state][v], dp[prev_state][u] + this->m_edges[this->m_graph[u][v]].cost);
                }
              }
            }
          }
        }
      }

      ::std::tuple<T, ::std::vector<::std::size_t>, ::std::vector<::std::size_t>> res;
      auto& [total_cost, vids, eids] = res;

      total_cost = dp[::tools::pow2(this->size()) - 1][0];
      if (total_cost == ::std::numeric_limits<T>::max()) return ::std::nullopt;

      ::std::size_t state = ::tools::pow2(this->size()) - 1;
      ::std::size_t v = 0;
      while (state > 0) {
        const auto prev_state = state & ~(static_cast<::std::size_t>(1) << v);
        for (::std::size_t u = 0; u < this->size(); ++u) {
          if (this->m_graph[u][v] < ::std::numeric_limits<::std::size_t>::max()) {
            if (dp[prev_state][u] < ::std::numeric_limits<T>::max() && dp[state][v] == dp[prev_state][u] + this->m_edges[this->m_graph[u][v]].cost) {
              vids.push_back(u);
              eids.push_back(this->m_graph[u][v]);
              state = prev_state;
              v = u;
              break;
            }
          }
        }
      }

      ::std::reverse(vids.begin(), vids.end());
      ::std::reverse(eids.begin(), eids.end());

      return res;
    }
  };
}


#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 8 "tests/tsp.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll V, E;
  std::cin >> V >> E;
  tools::tsp<true, ll> graph(V);
  for (ll i = 0; i < E; ++i) {
    ll s, t, d;
    std::cin >> s >> t >> d;
    graph.add_edge(s, t, d);
  }

  const auto res = graph.query();
  if (res) {
    const auto& [answer, vids, eids] = *res;
    assert_that(std::ssize(vids) == V);
    assert_that(std::ssize(eids) == V);
    ll sum = 0;
    for (ll i = 0; i < V; ++i) {
      assert_that(graph.get_edge(eids[i]).from == vids[i]);
      assert_that(graph.get_edge(eids[i]).to == vids[(i + 1) % V]);
      sum += graph.get_edge(eids[i]).cost;
    }
    assert_that(answer == sum);
    std::cout << answer << '\n';
  } else {
    std::cout << -1 << '\n';
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	4 MB
g++	00_sample_01.in	AC	4 ms	4 MB
g++	01_small_00.in	AC	4 ms	4 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	01_small_02.in	AC	4 ms	3 MB
g++	01_small_03.in	AC	4 ms	4 MB
g++	02_medium_00.in	AC	4 ms	4 MB
g++	02_medium_01.in	AC	4 ms	4 MB
g++	02_medium_02.in	AC	4 ms	4 MB
g++	02_medium_03.in	AC	4 ms	4 MB
g++	03_corner_00.in	AC	4 ms	4 MB
g++	03_corner_01.in	AC	12 ms	8 MB
g++	04_rand_00.in	AC	4 ms	4 MB
g++	04_rand_01.in	AC	4 ms	4 MB
g++	04_rand_02.in	AC	4 ms	4 MB
g++	04_rand_03.in	AC	4 ms	4 MB
g++	04_rand_04.in	AC	4 ms	4 MB
g++	04_rand_05.in	AC	4 ms	4 MB
g++	04_rand_06.in	AC	4 ms	4 MB
g++	04_rand_07.in	AC	4 ms	4 MB
g++	05_complete_00.in	AC	4 ms	4 MB
g++	05_complete_01.in	AC	4 ms	3 MB
g++	05_complete_02.in	AC	4 ms	4 MB
g++	05_complete_03.in	AC	4 ms	4 MB
g++	05_complete_04.in	AC	5 ms	4 MB
g++	05_complete_05.in	AC	5 ms	4 MB
g++	05_complete_06.in	AC	5 ms	4 MB
g++	05_complete_07.in	AC	6 ms	4 MB
g++	06_complete_rand_00.in	AC	4 ms	4 MB
g++	06_complete_rand_01.in	AC	4 ms	4 MB
g++	06_complete_rand_02.in	AC	4 ms	4 MB
g++	06_complete_rand_03.in	AC	5 ms	4 MB
g++	07_large_00.in	AC	5 ms	4 MB
g++	07_large_01.in	AC	6 ms	5 MB
g++	07_large_02.in	AC	6 ms	5 MB
g++	07_large_03.in	AC	8 ms	6 MB
g++	07_large_04.in	AC	14 ms	6 MB
g++	07_large_05.in	AC	14 ms	6 MB
g++	07_large_06.in	AC	26 ms	8 MB
g++	07_large_07.in	AC	26 ms	8 MB

Back to top page