Submission #6427000

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <functional>
#include <map>
#include <queue>
#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
using namespace std;
using ll = long long;
ll MOD = 1e9+7;

int n, a, b, m;
vector<int> G[101];
int dist[101];
ll cnt[101];

int main(int argc, const char * argv[]) {   
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    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){
//        for(int j = 0; j < G[i].size(); j++){
//            cout << G[i][j] << " ";
//        }
//        cout << endl;
//    }
    // init
    REP(i, n){
        dist[i] = 1e9;
        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){//goal
            break;
        }
        for(auto i = 0; i < G[u].size(); i++){
            int v = G[u][i];
            if(dist[v] == 1e9){
                dist[v] = dist[u] + 1;
                cnt[v] += cnt[u];
                cnt[v] %= MOD;
                q.push(v);
            }else if(dist[v] == dist[u] + 1){
                cnt[v] += cnt[u];
                cnt[v] %= MOD;
            }
        }
    }
    printf("%lld\n", cnt[b] % MOD);
    return 0;
}

Submission Info

Judge Result