AtCoder が提供しているABC（AtCoder Beginner Contest）338 のF問題をC++で解いてみました。ABC338は、2024年1月27日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Negative Traveling Salesman（Difficulty : 1834）
問題はリンク先をご覧ください。
ABC338 F問題 Negative Traveling Salesman
巡回セールスマン問題と同じように bitDP を使います。AtCoder Problems による Difficulty は 1835 でした。
解答案
負閉路が存在しないため、N頂点間の距離を Warshell Floyd 法で求めることができます。あとは、巡回セールスマン問題と同じです。ただし、巡回ではなく、すべての頂点を通る経路を考えます。
C++ プログラム例（ABC338F）
実装は、大きく分けて2つに分けられます。
- Warshell Floyd 法でN頂点間の距離を求めます。19から35行目は、定番コードです。
- 巡回セールス問題として解きます。
- どの頂点から始めてもよいため、すべての頂点から始まる重みを0に初期化します（38ー40行目）。
- 残りは、bitDP の定番コードです（41ー59行目）。
- すべての頂点を通る重みの最小値を出力します（61ー70行目）。
以下が、C++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
int main()
{
int n, m;
cin >> n >> m;
vector<int> u(m), v(m);
vector<ll> w(m);
for (int i = 0; i < m; ++i) {
cin >> u[i] >> v[i] >> w[i];
--u[i];
--v[i];
}
vector<vector<ll>> dist(n, vector<ll>(n, INF));
for (int i = 0; i < n; ++i) {
dist[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
dist[u[i]][v[i]] = w[i];
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if ((dist[i][k] < INF)&&(dist[k][j] < INF)) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
vector<vector<ll>> dp(1 << n, vector<ll>(n, INF));
for (int i = 0; i < n; ++i) {
dp[1 << i][i] = 0;
}
for (int i = 1; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
if ((i & (1 << j)) == 0) {
continue;
}
if (dp[i][j] == INF) {
continue;
}
for (int k = 0; k < n; ++k) {
if (dist[j][k] == INF) {
continue;
}
if ((i & (1 << k)) == 0) {
int v = (i | (1 << k));
dp[v][k] = min(dp[v][k], dp[i][j] + dist[j][k]);
}
}
}
}
ll result = INF;
for (int i = 0; i < n; ++i) {
result = min(result, dp[(1 << n) - 1][i]);
}
if (result == INF) {
cout << "No" << endl;
} else {
cout << result << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
今回は、Python版の紹介は省略します。
最後に
前日にABC301E問題（解説記事）を紹介しました。自分にとって、青Diffの問題は、かなり難しいと感じます。似た問題を続けて解くことによって、いつかコンテスト中に解ければと思います。
引き続き ABC の問題を紹介していきます。
