Submission #2551358

---

Source Code Expand

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const ll MOD = 1000000007;
const ll INF = 100000007;
const int MAX_N = 101;
vector<int> G[MAX_N];
bool used[MAX_N];
int dist[MAX_N];
ll cnt[MAX_N];

void dijkstra(int x, int n) {
    for(int i=0;i<n;i++) {
        dist[i] = INF;
    }
    priority_queue<P, vector<P>, greater<P> > pq;
    dist[x] = 0;
    pq.push(P(0, x));
    while (!pq.empty()) {
        P p = pq.top();pq.pop();
        used[p.second] = true;
        for (int i=0;i<G[p.second].size();i++) {
            if (!used[G[p.second][i]]) {
                dist[G[p.second][i]] = min(dist[G[p.second][i]], dist[p.second] + 1);
                pq.push(P(dist[G[p.second][i]], G[p.second][i]));
            }
        }
    }
}

void count_path(int x) {
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int cur = q.front();q.pop();
        if (used[cur]) continue;
        used[cur] = true;
        for (int i=0;i<G[cur].size();i++) {
            if (dist[cur] + 1 == dist[G[cur][i]]) {
                cnt[G[cur][i]] = (cnt[G[cur][i]] + cnt[cur]) % MOD;
                q.push(G[cur][i]);
            }
        }
    }
}

int main() {
    int a, b, n, m, x, y;
    cin >> n;
    cin >> a >> b;
    cin >> m;
    for (int i=0;i<m;i++) {
        cin >> x >> y;
        x--;y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    a--;b--;
    memset(used, false, sizeof(used));
    dijkstra(a, n);
    cnt[a] = 1;
    memset(used, false, sizeof(used));
    count_path(a);
    cout << cnt[b] << endl;
}

Submission Info

Judge Result