AtCoder が提供しているABC（AtCoder Beginner Contest）369 E問題をC++で解いてみました。ABC369は、2024年8月31日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Sightseeing Tour（Difficulty : 1301）
問題の詳細は、リンク先をご覧ください。
ワーシャル・フロイド法で頂点間の最短距離を求めて全探索します。AtCoder Problems による Difficulty は 1301 でした
解答案
大きく分けてプログラムを2つに分けます。
最初に、ワーシャル・フロイド（Warshell Floyd）法 を使って、すべての頂点間の最短距離を求めます。頂点数 $N$ の最大値は $400$ です。ワーシャル・フロイド法の計算量 $O(N^3) = 400^3 = 6.4 \times 10^7$ であるため、時間内に処理できます。
次に最大5つの橋（グラフの辺）を選びます。頂点 $1$ から頂点 $N$ までの経路で、この5つの橋を通る経路は、辺の端が2通りあるため、$5! \times 2^5 = 3840$ 通りあります。全探索して最小値を求めます。問い合わせは $3000$ 回ありますが、全体の計算量は、約 $1.6 \times 10^7$ となり、この計算も時間内に処理できます。
C++ プログラム例（ABC369E）
前半のワーシャル・フロイド法の実装は、定番コードです（42ー64行目）。同じ頂点を結ぶ2つ以上の橋があることに注意します（52、53行目の処理）。
$5! \times 2^5 = 3840$ 通りの全探索は再帰関数 rec として実装しました（18ー36行目）。使っている辺を used で管理して、端を指定しながら、次の辺を探します。端が2通りあるため、再帰呼び出しも2か所あります（30、31行目）。
少し長くなりましたが、以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
int n;
vector<vector<ll>> dist(400, vector<ll>(400, INF));
vector<int> u;
vector<int> v;
vector<ll> t;
int k;
vector<int> b;
vector<bool> used;
ll result;
void rec(int num, ll w, int from)
{
if (num == k) {
result = min(result, w + dist[from][n - 1]);
return;
}
for (int i = 0; i < k; ++i) {
if (used[i]) {
continue;
}
used[i] = true;
rec(num + 1, w + dist[from][u[b[i]]] + t[b[i]], v[b[i]]);
rec(num + 1, w + dist[from][v[b[i]]] + t[b[i]], u[b[i]]);
used[i] = false;
}
return;
}
int main()
{
int m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
dist[i][i] = 0;
}
u.resize(m);
v.resize(m);
t.resize(m);
for (int i = 0; i < m; ++i) {
cin >> u[i] >> v[i] >> t[i];
--u[i];
--v[i];
dist[u[i]][v[i]] = min(dist[u[i]][v[i]], t[i]);
dist[v[i]][u[i]] = min(dist[v[i]][u[i]], t[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]);
}
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> k;
b.resize(k);
for (int i = 0; i < k; ++i) {
cin >> b[i];
--b[i];
}
used.assign(k, false);
result = INF;
rec(0, 0, 0);
cout << result << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python版もコーディングしましたが、「Python (CPython 3.11.4)」、「Python (PyPy 3.10-v7.3.12)」のどちらも TLE 判定となりました。まだ Python に慣れていないため、記事での紹介を見送ります。
最後に
コンテスト中にこの問題を解くことができました。自分にとっての難易度は高く感じました。このようなことがあると、コンテスト参加を続けることができています。
ABC269からブログで紹介を始めて、この回で100回分のコンテストを紹介することができました（ABC316が欠番となっています）。
引き続き ABC の問題を紹介していきます。
