ABC 021 C - 正直者の高橋くん

問題

問題概要

省略

解法

bfsで解いた。よくある最短距離を求めるときにやる、bfsは一度、到達したところは2回目以降むしをするが、今回は、初めて到達したあとも、その位置に最短距離として、ほかの経路から到達して来る可能性があるので、bfsで初めに到達したときの最短距離をdistにメモしておき、それと同じコストでその位置までくるほかの経路があれば、その分も経路数として追加する。
dpぽいともいえるのか？cntに経路数をメモしている。

ミス

なし。

コード

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9, mod = 1e9 + 7;

int n, a, b, m;
vector<int> G[110];
int dist[110];//dist[i] := aからの最短距離
ll cnt[110];//cnt[i] := aからiまで最短距離でくる個数
int main(void){
    cin >> n >> a >> b >> m;
    a--; b--;
    rep(i, m){
        int x, y; cin >> x >> y;
        x--; y--;
        G[x].push_back(y); G[y].push_back(x);
    }
    rep(i, n){
        dist[i] = INF;
        cnt[i] = 0;
    }

    queue<int> q;
    q.push(a);
    dist[a] = 0; cnt[a] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        if(u == b) break;
        for(auto v : G[u]){
            if(dist[v] == INF){//初めての到達
                dist[v] = dist[u] + 1;
                (cnt[v] += cnt[u]) %= mod;
                q.push(v);
            }else if(dist[v] == dist[u] + 1){//ほかにも最短経路が存在
                (cnt[v] += cnt[u]) %= mod;
            }
        }
    }
    printf("%lld\n", cnt[b] % mod);
    return 0;
}