 # PROBLEM LINK:

Author: Sunita Sen
Tester: Sandeep Singh, Akash Kumar Bhagat
Editorialist: Sunita Sen

EASY - MEDIUM

BFS

# PROBLEM:

Given a graph with N nodes, M of which can be visited. Find the shortest path from A to B.

# QUICK EXPLANATION:

Remove every edge which is connected to a building which does not have a treat. Then find the shortest path using BFS.

# EXPLANATION:

We can treat the city as a graph with N nodes, and P cities.
We can observe that any building which does not have a treat is useless. Hence, while forming the graph we can skip any edge which connects to any such building.
We will be left with a subset of the input graph.
And now we will have to use BFS to find the shortest path from A to B.

Time Complexity: O(M + P)

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(u, vis) memset(u, vis, sizeof(u))
#define ll long long
#define ull unsigned long long
#define MOD  1000000007
#define MAX  1e9
#define pb   push_back
#define F    first
#define S    second

vector<ll> v;
ll dist;
bool visited;

void bfs(ll s){
queue<ll> q;
q.push(s);
visited[s] = true;
dist[s] = 0;
while(!q.empty()){
ll p = q.front();
q.pop();
for(auto i:v[p]){
if(!visited[i]){
dist[i] = dist[p]+1;
q.push(i);
visited[i] = true;
}
}
}
}

signed main() {
ll t=1;
cin>>t;
while(t--){
mem(v,0);
mem(visited,false);
mem(dist,-1);
ll n,m;
cin>>n>>m;
ll a[m];
unordered_map<ll,ll> mp;
rep(i,m){
cin>>a[i];
mp[a[i]]++;
}
ll p;
cin>>p;
rep(i,p){
ll r, s;
cin>>r>>s;
if(mp.find(r) != mp.end() && mp.find(s) != mp.end()){
v[r].pb(s);
v[s].pb(r);
}
}
ll A,B;
cin>>A>>B;

bfs(A);
cout<<dist[B]<<endl;

}

}
``````
1 Like