C++ Library for Competitive Programming
/*
* @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;
}