Submission #24506510

---

Source Code Expand

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;

#define F first
#define S second
#define debug(x) cout<<x<<endl
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pb push_back
#define mp make_pair
#define pi acos(-1)
// __int128->GNU G++ 17 9.2.0 Codeforces (but doesnot use with cout cin And cant take direct input use normal datatype the typecast ) 
using ll = long long;
const ll M = 1000000007;
const ll M1= 998244353;
using vl = vector<ll>;
using pll =  pair<ll,ll>;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


//https://codeforces.com/blog/entry/20935
//https://www.hackerrank.com/contests/mit-open-20-finals/challenges/fractions-arent-tough-or-are-they
//
// typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> is;


// ll power(ll x,ll y){
//     if(y==0)
//         return 1;
//     ll res=power(x,y/2);
//     res=(res*res);
//     if(y&1)
//         res=(res*x);
//     return res;
// }
ll powermod(ll x,ll y,ll mod){
    if(y==0)
        return 1;
    ll res=powermod(x,y/2,mod);
    res=(res*res)%mod;
    if(y&1)
        res=(res*x)%mod;
    return res;
}

void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> gr(n+1);
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        gr[a].pb(b);
        gr[b].pb(a);
    }
    vector<int> dis(n+1),vis(n+1,0);
    vector<vector<int>> v(n+1);
    dis[1]=0;
    queue<int> q;
    q.push(1);
    vis[1]=1;
    while(!q.empty()){
        int no=q.front();
        q.pop();
        for(int i:gr[no]){
            if(vis[i]==0){
                q.push(i);
                dis[i]=dis[no]+1;
                v[dis[i]].pb(i);
                vis[i]=1;
            }
        }
    }
    if(vis[n]==0){
        cout<<0<<endl;
        return;
    }
    vector<ll> dp(n+1,0);
    for(int i:v[1])
        dp[i]=1;
    for(int i=2;i<=dis[n];i++){
        for(int j:v[i])
        {
            for(int k:gr[j])
                if(dis[k]==i-1){
                    dp[j]+=dp[k];
                    dp[j]%=M;
                }
        }  
    }
    cout<<dp[n]<<endl;
}   
int main(){ 
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //sieve();
    
    int test=1; 
    //cin>>test;
    for(int i=1;i<=test;i++)
    {//cout<<"Case #"<<i<<": ";
    solve();}
    return 0;
}

Submission Info

Judge Result