For the above question i am trying DFS approach to check whether the required vertex is reachable or not from given initial vertex.
I am first creating a bidirectional graph for it.
Node of the graph is the ID of the frog and edge weight represents the distance of ith frog to i+1th frog .
i am connecting ith node to jth node only if j is the next nearest (for this array of pairs is first sorted with distance as second paramater)
so nodes are connected pair wise
I have created a dummy 0th node which connects to 1st node with 0 distance to avoid confusion of 1 based indexing here.
according to my approach following graph gets formed: (middle italic number is weight)
weight: distance of i to j and vice versa
0<–0 ->1<–3–>2<–2–>4<–3–>3<–4–>5
please have a look at my implementation
#include <bits/stdc++.h>
#define pi pair<int,int>
using namespace std;
bool isReachable(vector<pi> g[],int s,int target,int k,bool vis[]){
vis[s]=true;
vector<pi>::iterator it;
for(it=g[s].begin();it!=g[s].end();it++){
if(it->first==target && it->second<=k)
return true;
if(!vis[it->first] && it->second<=k)
return isReachable(g,it->first,target,k,vis);
}
return false;
}
bool comp(pair<int,int> p,pair<int,int> q){
return p.second<q.second;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,k,p,x,u,v,d,i,prev=0;
cin>>n>>k>>p;
vector<pi> arr;
vector<pi> graph[n+1];
for(int i=1;i<=n;i++){
cin>>x;
arr.push_back({i,x});
}
sort(arr.begin(),arr.end(),comp);
graph[0].push_back({1,0});
graph[1].push_back({0,0});
for(i=0;(i+1)<n;i++){
u=arr[i].first;
v=arr[i+1].first;
d=abs(arr[i+1].second-arr[i].second);
graph[u].push_back({v,d});
graph[v].push_back({u,d});
}
while(p--){
cin>>u>>v;
bool visited[n+1];
for(int i=0;i<=n;i++){
visited[i]=false;
}
visited[0]=true;
if(isReachable(graph,u,v,k,visited))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
It is giving correct output for the given test cases , but wrong on submission.