Submission #6426183

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
#define test cout<<"test"<<endl;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}
//m.emplace(x,0).fi->second++;

vector<vector<ll>>G(100001);
vector<ll>d(100001);
vector<ll>l(100001);
void bfs(ll k){
  queue<tuple<ll,ll,ll>> q;
  d[k]=1;
  for(ll i=0;i<G[k].size();i++){
      if(d[G[k][i]]==0){
        q.push(make_tuple(G[k][i],1,k));  
        l[G[k][i]]=1;
      }
  }
  while(!q.empty()){
    ll x=get<0>(q.front());
    ll len=get<1>(q.front());
    ll pre=get<2>(q.front());
    if(d[x]==0)
    for(ll i=0;i<G[x].size();i++){
      if(d[G[x][i]]==0){
        q.push(make_tuple(G[x][i],len+1,x)); 
        if(l[G[x][i]]==0)l[G[x][i]]=len+1; 
      }
    }
    if(len==l[x])pmod(d[x],d[pre]);
    //cout<<x spa d[x] spa len spa l[x] spa pre<<endl;
    q.pop();
  }
}

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll n,a,b,m;cin>>n>>a>>b>>m;
  for(i=0;i<m;i++){
    ll p,q;
    cin>>p>>q;
    G[p].push_back(q);
    G[q].push_back(p);
  }
  bfs(a);
  cout<<d[b]<<endl;
  return 0;
}

Submission Info

Judge Result