Submission #2998884

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

const lint mod = 1e9 + 7;
lint emod(lint a) { return (a % mod + mod) % mod; }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, a, b, m; cin >> n >> a >> b >> m, a--, b--;
  VV<> g(n);
  for (int i = 0; i < m; i++) {
    int x, y; cin >> x >> y, x--, y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  V<lint> num(n);
  V<> d(n, 1000);
  V<> vis(n);
  queue<int> q;
  num[a] = 1;
  d[a] = 0;
  q.push(a);
  while (!q.empty()) {
    int v = q.front(); q.pop();
    if (vis[v]) continue;
    vis[v] = 1;
    for (auto&& i : g[v]) {
      if (d[i] < d[v] + 1) continue;
      d[i] = d[v] + 1;
      num[i] = (num[i] + num[v]) % mod;
      q.push(i);
    }
  }
  cout << emod(num[b]) << '\n';
}

Submission Info

Judge Result