C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/巡回セールスマン問題 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A */ #include <iostream> #include <limits> #include <vector> #include "emthrm/graph/edge.hpp" #include "emthrm/graph/traveling_salesman_problem.hpp" int main() { constexpr int INF = std::numeric_limits<int>::max(); int v, e; std::cin >> v >> e; std::vector<std::vector<emthrm::Edge<int>>> g(v); while (e--) { int s, t, d; std::cin >> s >> t >> d; g[s].emplace_back(s, t, d); } const int ans = emthrm::traveling_salesman_problem(g, INF); std::cout << (ans == INF ? -1 : ans) << '\n'; return 0; }
#line 1 "test/graph/traveling_salesman_problem.test.cpp" /* * @title グラフ/巡回セールスマン問題 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A */ #include <iostream> #include <limits> #include <vector> #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 1 "include/emthrm/graph/traveling_salesman_problem.hpp" #include <algorithm> #line 6 "include/emthrm/graph/traveling_salesman_problem.hpp" #include <numeric> #line 8 "include/emthrm/graph/traveling_salesman_problem.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 10 "include/emthrm/graph/traveling_salesman_problem.hpp" namespace emthrm { template <typename CostType> CostType traveling_salesman_problem( const std::vector<std::vector<Edge<CostType>>>& graph, const CostType inf = std::numeric_limits<CostType>::max()) { const int n = graph.size(); if (n == 1) [[unlikely]] return 0; std::vector<std::vector<CostType>> dp(1 << n, std::vector<CostType>(n, inf)); dp[1][0] = 0; for (int i = 1; i < (1 << n); ++i) { for (int j = 0; j < n; ++j) { if (dp[i][j] == inf) continue; for (const Edge<CostType>& e : graph[j]) { if (i >> e.dst & 1) continue; dp[i | (1 << e.dst)][e.dst] = std::min(dp[i | (1 << e.dst)][e.dst], dp[i][j] + e.cost); } } } CostType res = inf; for (int j = 1; j < n; ++j) { if (dp.back()[j] == inf) continue; for (const Edge<CostType>& e : graph[j]) { if (e.dst == 0) res = std::min(res, dp.back()[j] + e.cost); } } return res; } } // namespace emthrm #line 13 "test/graph/traveling_salesman_problem.test.cpp" int main() { constexpr int INF = std::numeric_limits<int>::max(); int v, e; std::cin >> v >> e; std::vector<std::vector<emthrm::Edge<int>>> g(v); while (e--) { int s, t, d; std::cin >> s >> t >> d; g[s].emplace_back(s, t, d); } const int ans = emthrm::traveling_salesman_problem(g, INF); std::cout << (ans == INF ? -1 : ans) << '\n'; return 0; }