ECJN205 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

EASY - MEDIUM

PREREQUISITES:

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[100000];
ll dist[100000]; 
bool visited[100000]; 


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