Submission #6421140

---

Source Code Expand

#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */
const int MOD = 1e9+7;
int main() {
  ll n,a,b,m; cin >> n >> a >> b >> m;
  a--; b--;
  vector<int> visited(n, 0);
  vector<int> dist(n, 0);
  vector<vector<int>> g(n, vector<int>(n,0));
  vector<ll> dp(n,0);
  REP(i,m){
    ll x,y; cin >> x >> y;
    x--; y--;
    g[x][y] = 1;
    g[y][x] = 1;
  }
  queue<ll> q;
  q.push(a);
  dp[a] = 1;
  visited[a] = 1;
  while(!q.empty()){
    ll cv = q.front();
    q.pop();
    REP(nv, n) {
      if(g[cv][nv]==0) continue;
      if(visited[nv] == 0){
        dist[nv] = dist[cv] + 1;
        visited[nv] = 1;
        q.push(nv);
      }
      if(dist[nv] == dist[cv]+1)(dp[nv] += dp[cv]) %= MOD;
    }
    // REP(i, n){
    //   DUMP(i); DUMP(dp[i]);
    // }
    // cout << "----------" << endl;
  }
  cout << dp[b] << endl;
  
}

Submission Info

Judge Result