AtCoder が提供しているABC（AtCoder Beginner Contest）022 C問題をC++で解いてみました。ABC022は、2015年4月25日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Blue Bird（Difficulty : 1505（参考値））
問題の詳細は、リンク先をご覧ください。
最初の頂点を除いたグラフ内のすべての頂点間の最短距離を求めて、最初の経路と最後の経路を含む経路を全探索します。AtCoder Problems による Difficulty は 1505（参考値）でした。
解答案
C++ プログラム例（ABC022C）
最初の頂点（高橋君の家）を始点と終点とする一周の経路が対象となります。同じ辺を通らないようにするため、この一周の経路を以下のように分解します。
- 最初の経路
- 2番目の頂点から（経路の長さ-1）番目の頂点を結ぶ経路
- 最後の経路
最初の頂点とそれにつながる辺を除いたグラフのすべての頂点間の最短距離は、ワーシャル・フロイド法で求めることができます（37ー45行目）。ワーシャル・フロイド法は、頂点数が300個以内であれば計算量 $O(N^3) = 2.7 \times 10^7$ となり、十分に実行可能です。
次に、最初の頂点から出発する辺を2つ選び、それらの長さと、その先の頂点間の最短距離の合計の最小値を求めます（47ー53行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
struct Edge {
int to;
ll weight;
Edge() {}
Edge(int t, ll w) : to(t), weight(w) {}
};
int main()
{
int n, m;
cin >> n >> m;
vector<Edge> G;
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) {
int u, v, l;
cin >> u >> v >> l;
--u;
--v;
if (u == 0) {
G.push_back(Edge(v, l));
} else if (v == 0) {
G.push_back(Edge(u, l));
} else {
dist[u][v] = l;
dist[v][u] = l;
}
}
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]);
}
}
}
}
ll result = INF;
for (int i = 0; i < (int)G.size(); ++i) {
for (int j = i + 1; j < (int)G.size(); ++j) {
ll t = G[i].weight + G[j].weight + dist[G[i].to][G[j].to];
result = min(result, t);
}
}
if (result == INF) {
cout << -1 << endl;
} else {
cout << result << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
最初の頂点を除くグラフ内の全ての頂点間の最短経路を求めることがポイントでした。一周の経路を、一本道とその始点および終点の経路に分解して考える方法は、非常に勉強になりました。
引き続き ABC の問題を紹介していきます。
