Submission #24513471

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, n) for (auto i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()

using namespace std;

using ll = long long int;
using Graph = vector<vector<int>>;

const int MOD_NUM = 1e9 + 7;

template <class T>
vector<T> input_vec(int N) {
    vector<T> result(N);
    rep(i, N) cin >> result[i];
    return result;
}

int main() {
    // Input
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    rep(i, M) cin >> A[i] >> B[i];

    // Process
    Graph graph(N);
    rep(i, M) {
        graph[A[i] - 1].emplace_back(B[i] - 1);
        graph[B[i] - 1].emplace_back(A[i] - 1);
    }

    vector<int> costs(N, N);
    vector<ll> counts(N, 0);
    costs[0] = 0;
    counts[0] = 1;
    queue<int> que;
    que.push(0);
    while (!que.empty()) {
        int current = que.front();
        que.pop();

        int current_cost = costs[current] + 1;
        for (int next : graph[current]) {
            if (current_cost > costs[next]) continue;

            if (current_cost < costs[next]) {
                costs[next] = current_cost;
                counts[next] = 0;
                que.push(next);
            }

            counts[next] += counts[current];
            counts[next] %= MOD_NUM;
        }
    }

    ll ans = counts[N - 1];

    // Output
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result