ABC021 - C - 正直者の高橋くん

探索！となるとBFSよりDFS採用しようかなと思いがち。

解説ACです。

問題

atcoder.jp

考えたこと

はじまりの街からの距離をそれぞれ調べていって、距離１の街の個数 * 距離２の街の個数 *......でいいかなと思ったけど、途中から枝に入っていってどん詰まりになったら、そのルートは間違ってる頃になるからどうしようかな、とか考えてた。

末端まで行って枝だったら距離を-1とかにしつつ選択肢から外していこうかなとか思ったけど、どこまで戻ればいいかわからないしね。

解答

この人の解説を参考にした。

mmxsrup.hatenablog.com

BFSで終わりの街まで「今の街への経路はなんパターンか？」を足しながら流していくと良かった。ただし、別ルートから来ることもあるので、すでに訪問済でも訪問距離が同じなら回数を足し合わせるようにする必要がある。

ソースを開く

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

int main(){

    long mod = 1000000007;

    long n,a,b;
    cin >> n >> a >> b;
    a--;
    b--;
    
    vector<vector<long>> Graph(n);

    long m;
    cin >> m;

    rep(i,m){
        long x,y;
        cin >> x >> y;
        x--;
        y--;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }

    vector<long>    path_cnt(n,0);
    vector<long>    dist(n, -1);

    queue<long> q;
    q.push(a);
    dist[a] = 0;
    path_cnt[a] = 1;

    while(q.size()){
        long cur = q.front();
        q.pop();

        if(cur == b){
            // 目的地ならそこからどこにも行かない。
            // 別ルートでBに行くかもしれないのでbreakではなくcontinueにする
            continue;
        }
        long d = dist[cur];
        long p = path_cnt[cur];

        for(auto it : Graph[cur]){

            // 未到達の場合
            if(dist[it] == -1){
                // 距離を入れて、経路数を入れる。
                // BFSなので、今が最小になっている。
                dist[it] = d + 1;
                path_cnt[it] = p % mod;
                q.push(it);
            } else if(dist[it] == d + 1){
                // 到達済の場合
                // こんかいも最短距離なら、パスの数を追加する。
                path_cnt[it] = (p + path_cnt[it]) % mod;
            }
        }
    }

    cout << path_cnt[b] << endl;


    return 0;
}

学んだこと

• 最短距離ならBFSで見つけれる。

感想

学んだことっていうか思い出したことだよね。一時期サボっていたタイミングで忘れてしまった。BFSはすらすらとかけたのでよかった。