Submission #2374443

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using pi = pair<int,int>;

const int MAX = 101;
const int INFTY = 2e9;
const int WHITE = 1;
const int GRAY = 2;
const int BLACK = 3;
const int MOD = 1e9+7;

pi dist[MAX];
int G[MAX][MAX];
int color[MAX];

int N;

int bfs(int a, int b){
    for(int i=0;i<N;i++){
        dist[i].first = INFTY;
        dist[i].second = 0;
        color[i] = WHITE;
    }
    dist[a].first = 0;
    dist[a].second = 1;
    color[a] = BLACK;
    queue<int> Q;
    Q.push(a);

    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        color[u] = BLACK;
        for(int v=0;v<N;v++){
            if(G[u][v] == 0) continue;
            if(color[v] == BLACK) continue;
            if(dist[v].first > dist[u].first + 1){
                dist[v].first = dist[u].first + 1;
                dist[v].second = dist[u].second;
                Q.push(v);
                color[v] = GRAY;
            }else if(dist[v].first == dist[u].first + 1){
                (dist[v].second += dist[u].second) %= MOD;
                color[v] = GRAY;
            }
        }
    }
    return dist[b].second;
}

int main(){
    cin >> N;
    int a,b; cin >> a >> b;
    a--; b--;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            G[i][j] = 0;
        }
    }
    int M; cin >> M;
    for(int i=0;i<M;i++){
        int x,y; cin >> x >> y;
        x--; y--;
        G[x][y] = 1; G[y][x] = 1;
    }

    cout << bfs(a,b)%MOD << endl;

    return 0;
}

Submission Info

Judge Result