AtCoder が提供しているABC（AtCoder Beginner Contest）012 D問題をC++で解いてみました。ABC012は、2014年7月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 バスと避けられない運命（Difficulty : 1166（参考値））
問題の詳細は、リンク先をご覧ください。
全ての頂点から残りの頂点への最短経路を求める問題です。AtCoder Problems による Difficulty は 1166（参考値）でした。
解答案
C++ プログラム例（ABC012D）
すべてのバス停から残りのバス停への最短時間を求める必要があります。ワーシャル–フロイド（Warshell Floyd）法は、頂点数 $N$ に対して、計算量 $O(N^3)$ でこの値を求めることができます。このアルゴリズムは、過去の記事で解説しています。11～32行目は、ワーシャル-フロイド法の定番コードとなります。
各バス停について、他のバス停への最短時間の最大値を計算します。その中で最小の値を出力します（34ー41行目）。
以下が、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<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 a, b, t;
cin >> a >> b >> t;
--a;
--b;
dist[a][b] = t;
dist[b][a] = t;
}
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 < n; ++i) {
ll t_max = 0;
for (int j = 0; j < n; ++j) {
t_max = max(t_max, dist[i][j]);
}
result = min(result, t_max);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
ワーシャル–フロイド法が利用できる典型問題でした。
引き続き ABC の問題を紹介していきます。
