HackerEarth Mancunian And Nancy Play A Game problem solution

In this HackerEarth Mancunian And Nancy Play A Game problem solution Mancunian is in a committed relationship with his girlfriend Nancy. His idea of a date is for them to have a romantic candlelight dinner and then play graph games. This time they are using a graph of N nodes and E edges. Mancunian is located at vertex M1 and wants to move to M2. Nancy wants to move from vertex N1 to N2. Anyone can move at any time, till both have reached their respective destinations. But there is a catch. Nancy can’t bear to be too far away from her true love, Mancunian and hence the shortest distance between them at any point in time should never exceed a specified parameter K.

You are given several possible pairs of N1, N2 for Nancy. Count the number of such pairs which will make a valid game (where both Mancunian and Nancy can reach their respective destinations without violating the distance condition).

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;


#define N 100005
int n, s1, t1, s2, t2, k, dist[2][N];
vector<int> adj[N];


bool is_connected(int u, int v){

    memset(dist, -1, sizeof(dist));
    queue<int> qq;
    dist[0][u] = 1;
    qq.push(u);
    while(!qq.empty()){

        int v = qq.front();
        qq.pop();
        for(int i=0;i<(int)adj[v].size();i++){
            int vv = adj[v][i];
            if(dist[0][vv] == -1){
                dist[0][vv] = 1;
                qq.push(vv);
            }
        }
    }
    return (dist[0][v] == 1);
}


void bfs(int idx, int src){

    queue<int> qq;
    dist[idx][src] = 0;
    qq.push(src);
    while(!qq.empty()){

        int v = qq.front();
        qq.pop();
        for(int i=0;i<(int)adj[v].size();i++){
            int vv = adj[v][i];
            if(dist[idx][vv] == -1){
                dist[idx][vv] = 1+dist[idx][v];
                qq.push(vv);
            }
        }
    }

    for(int i=1;i<=n;i++)
        if(dist[idx][i] == -1)
            dist[idx][i] = MOD;
}


int main(){

    int e;
    scanf("%d%d%d", &n, &e, &k);
    while(e--){
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].pb(b);
        adj[b].pb(a);
    }
    scanf("%d%d", &s1, &t1);

    int q, ans = 0;
    scanf("%d", &q);

    bool valid = is_connected(s1, t1);
    memset(dist, -1, sizeof(dist));
    bfs(0, s1);
    bfs(1, t1);

    while(q--){

        int s2, t2;
        scanf("%d%d", &s2, &t2);

        if(valid && dist[0][s2] <= k && dist[1][t2] <= k)   ans++;
    }

    printf("%dn", ans);
    return 0;
}