AtCoder が提供しているABC（AtCoder Beginner Contest）021 C問題をC++で解いてみました。ABC021は、2015年4月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 正直者の高橋くん（Difficulty : 1324（参考値））
問題の詳細は、リンク先をご覧ください。
最短経路を求めてから、DPで経路数を求めます。AtCoder Problems による Difficulty は 1324（参考値）でした。
解答案
C++ プログラム例（ABC021C）
町 $a$ から、それ以外の町への最短経路は、BFS で求めることができます。町 $a$ からの最短経路の数を dp とします。距離が短い町から、経路の数を加えていきます。漸化式は以下となります。
dp[ある町] = $\sum$ dp[その町への経路があり距離が１短い町]
dp[a] ＝1、それ以外の場合は、0 を初期値とします。
プログラムの補足です。
- BFS で町 $a$ からの最短経路を求めます（20ー33行目）。
- 最短経路の距離をインデックスとしてそ距離を持つ町を配列
v_distに格納します（35ー38行目）。 - 配列
dpを上の漸化式に従い加えていきます。数が大きくなるため、$1000000007$ で剰余を取ります（40ー51行目）。
dp[b] の値が解答となります。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int main()
{
int n, a, b;
cin >> n >> a >> b;
vector<vector<int>> G(n + 1);
int m;
cin >> m;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
vector<int> dist(n + 1, -1);
queue<int> que;
que.push(a);
dist[a] = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v] == -1) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}
vector<vector<int>> v_dist(n + 1);
for (int i = 1; i <= n; ++i) {
v_dist[dist[i]].push_back(i);
}
vector<int> dp(n + 1, 0);
dp[a] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < (int)v_dist[i].size(); ++j) {
for (auto e : G[v_dist[i][j]]) {
if (dist[e] == i - 1) {
dp[v_dist[i][j]] += dp[e];
dp[v_dist[i][j]] %= MOD;
}
}
}
}
cout << dp[b] << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
BFS で最短経路を求めてから、DP で経路数を求める応用問題でした。
引き続き ABC の問題を紹介していきます。
