個人的に解いていて面白かった問題を解説していきます。
今回はABC021C-正直者の高橋くんを部分に分けて解説します
個人的には複数個のアルゴリズムを使って解く問題が解きごたえがあるのでそのような問題を多く解説すると思います。
この問題を要約するとN頂点M辺の重みなし無向グラフが与えられてある頂点Aからある頂点Bまでの最短距離が何通りあるかを求めてそれを1000000007で割ったあまりにする問題です。
そしてこの問題の主な解法はBFSと動的計画法です。
1.グラフを作る
まずは頂点数Nと辺数M,始点、終点を入力します。
その後にN頂点の隣接リストを作ります。
M回2つの点を入力してその点を結ぶということをします。
この部分のコード
// 頂点数、辺数を入力して隣接リストを作る
int N, M, from, to;
cin >> N >> from >> to >> M;
from--, to--; // 0-inidexedなので1引く
vector<vector<int>> graph(N);
// M回入力する
for (int i = 0; i < M; i++){
int u, v;
cin >> u >> v;
u--, v--; // 0-inidexedなので1引く
graph[u].push_back(v);
graph[v].push_back(u);
}
2.BFSで最短距離を求める
一通り入力が終わったあとはBFSを使って始点から終点までの最短距離を求めます。
C++ではqueueというデータ構造を使ってBFSをします。
詳しくはけんちょんさんの記事を見てください。
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
また、最短距離を管理する配列を作ってそこに最短距離を記録していきます。
そしてもう新しく行ける点がなくなった(またはもう終点についた)らBFSを終了します。
この部分のコード
// queueと最短距離を管理する配列を作る
queue<int> Q;
vector<int> dist(N, -1);
// 初期値を代入する
Q.push(from);
dist[from] = 0;
// BFS本体
// while (!Q.empty() && dist[to] == -1) でも良い
while (!Q.empty()){
// Qの最初の値を取り出す
int now = Q.front();
Q.pop();
// その点から行ける場所を探索する
for (int i : graph[now]){
if (dist[i] == -1){
// まだ訪れていなければその部分の距離を更新
Q.push(i);
dist[i] = dist[now]+1;
}
}
}
3.動的計画法で何通りかを書く
次は動的計画法を使って最短経路が何通りあるかを数えていきます。
まずNこの配列を(最短距離+1)この2次元配列を作ります。
今回のdp[i][j]というのはi回目に頂点jへ行く通り数のことです。
ただ、この場合は1000000007で割ったあまりを出力するつまり答えが非常に大きくなるということなので型をintではなくlong longを使いましょう。
この部分のコード
int shortest = dist[to];
vector<vector<long long>> dp(shortest+1, vector<long long>(N, 0)); // DP用の配列を作る
dp[0][from] = 1; // 初期値
// DP本体
for (int i = 0; i < shortest; i++){
for (int j = 0; j < N; j++){
// 行ける場所に行って通り数を足す
for (int k : graph[j]){
dp[i+1][k] += dp[i][j];
}
}
}
4.出力する
1000000007で割ってから出力しましょう
この部分のコード
cout << dp[shortest][to]%1000000007 << endl;
return 0;
解答例
これを全部合わせたものがこれです
#include <bits/stdc++.h>
using namespace std;
int main(){
// 入力層
// 頂点数、辺数を入力して隣接リストを作る
int N, M, from, to;
cin >> N >> from >> to >> M;
from--, to--; // 0-inidexedなので1引く
vector<vector<int>> graph(N);
for (int i = 0; i < M; i++){
int u, v;
cin >> u >> v;
u--, v--; // 0-inidexedなので1引く
graph[u].push_back(v);
graph[v].push_back(u);
}
// BFS層
// queueと最短距離を管理する配列を作る
queue<int> Q;
vector<int> dist(N, -1);
// 初期値を代入する
Q.push(from);
dist[from] = 0;
// BFS本体
// while (!Q.empty() && dist[to] == -1) でも良い
while (!Q.empty()){
// Qの最初の値を取り出す
int now = Q.front();
Q.pop();
// その点から行ける場所を探索する
for (int i : graph[now]){
if (dist[i] == -1){
// まだ訪れていなければその部分の距離を更新
Q.push(i);
dist[i] = dist[now]+1;
}
}
}
// DP層
int shortest = dist[to];
vector<vector<long long>> dp(shortest+1, vector<long long>(N, 0)); // DP用の配列を作る
dp[0][from] = 1; // 初期値
// DP本体
for (int i = 0; i < shortest; i++){
for (int j = 0; j < N; j++){
// 行ける場所に行って通り数を足す
for (int k : graph[j]){
dp[i+1][k] += dp[i][j];
}
}
}
// 出力層
cout << dp[shortest][to]%1000000007 << endl;
return 0;
}
これを書いているときに思ったのが最初から動的計画法でも行けるかもしれないと思ったので後で確かめてみます。
確かめたらコメントに記載するのでそれも合わせて読んでくれると嬉しいです。