AtCoder が提供しているABC（AtCoder Beginner Contest）073 D問題をC++で解いてみました。ABC073は、2017年9月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 joisino’s travel（Difficulty : 1345）
問題の詳細は、リンク先をご覧ください。
すべての町の間の最短距離を求めて順列全探索します。AtCoder Problems による Difficulty は 1345 でした。
解答案
C++ プログラム例（ABC073D）
前準備としてすべての町の間の最短距離を求めます。町の数
次にすべての順列について全探索します。next_permutation を用います。順列の長さ
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int n, m, R;
cin >> n >> m >> R;
vector<int> r(R);
for (int i = 0; i < R; ++i) {
cin >> r[i];
--r[i];
}
vector<vector<int>> dist(n, vector<int>(n, INF));
for (int i = 0; i < n; ++i) {
dist[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a;
--b;
dist[a][b] = c;
dist[b][a] = c;
}
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<int> p(R);
for (int i = 0; i < R; ++i) {
p[i] = i;
}
int result = INF;
do {
int t_result = 0;
for (int i = 0; i < R - 1; ++i) {
t_result += dist[r[p[i]]][r[p[i + 1]]];
}
result = min(result, t_result);
} while (next_permutation(p.begin(), p.end()));
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
2つの典型手法を組み合わせる良問だと思います。
引き続き ABC の問題を紹介していきます。
