ABC021 C問題 正直者の高橋くん

最短経路の組み合わせの数を求める問題。
完全に発想が凝り固まっててすごい時間がかかった…。

頭の中で考えてるうちは、普通に始点からつながっているところの組み合わせを更新していくだけじゃ無駄に数えてしまいそうだなぁとか考えていたけど、手を動かしてシュミレートしてみたらそれが最適解だった…
何事も手を動かすことが大事ですね…。

int N;
int a, b;
int M;
bool G[101][101];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    cin >> a >> b;
    a--; b--;
    cin >> M;
    memset(G, false, sizeof(G));
    for(int i=0; i<M; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x][y] = true;
        G[y][x] = true;
    }
    int C[101][101];
    memset(C, 0, sizeof(C));
    C[0][a] = 1;
    for(int i=1; i<101; i++){
        for(int j=0; j<101; j++){
            for(int k=0; k<101; k++){
                if(G[j][k]){
                    C[i][j] += C[i-1][k];
                    C[i][j] %= 1000000007;
                }
            }
        }
        if(C[i][b]){
            cout << C[i][b] << endl;
            return 0;
        }
    }

}