In this HackerEarth Monk and the Islands problem solution Monk visits the land of Islands. There are a total of N islands numbered from 1 to N. Some pairs of islands are connected to each other by Bidirectional bridges running over water.
Monk hates to cross these bridges as they require a lot of efforts. He is standing at Island #1 and wants to reach the Island #N. Find the minimum the number of bridges that he shall have to cross, if he takes the optimal route.
HackerEarth Monk and the Islands problem solution.
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long int
#define elif else if
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
int n,m;
vector< vector<int> >gr;
int visi[10005]={0};
int bfs()
{
queue<pii>mq;
memset(visi,0,sizeof(visi));
mq.push(mp(1,0));
visi[1]=1;
while(!mq.empty())
{
pii tmp=mq.front();
mq.pop();
int v=tmp.first,c=tmp.second;
visi[v]=2;
if(v==n)return c;
for(int i=0;i<gr[v].size();i++)
{
int tn=gr[v][i];
if(visi[tn]>0)continue;
mq.push(mp(tn,c+1));
visi[tn]=1;
if(tn==n)
return c+1;
}
}
return -1;
}
int main()
{
freopen("in","r",stdin);
freopen("out","w",stdout);
int t;
cin>>t;
assert(1<=t && t<=10);
while(t--)
{
gr.clear();
int i,j;
cin>>n>>m;
assert(1<=n && n<=10000);
assert(1<=m && m<=100000);
assert(m<=n*n);
gr.resize(n+1);
rep(i,m)
{
int ta,tb;
cin>>ta>>tb;
if(find(gr[ta].begin(),gr[ta].end(),tb)!=gr[ta].end())
continue;
gr[ta].pb(tb);
gr[tb].pb(ta);
}
int ans=bfs();
cout<<ans;
assert(ans>=0 && ans<n);
if(t>0)cout<<"n";
}
return 0;
}
Second solution
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> II;
typedef vector< II > VII;
typedef vector<int> VI;
typedef vector< VI > VVI;
typedef long long int LL;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))
#define si(n) scanf("%d",&n)
#define dout(n) printf("%dn",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lldn",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
const int N = int(1e4)+1;
const int M = int (1e5)+1;
VI g[N];
int dist[N];
int vis[N];
int main()
{
int t;si(t);
assert(t<=10);
while(t--)
{
int n,m;
si(n);si(m);
assert(n<N);
assert(m<M);
for(int i=0;i<m;i++)
{
int u,v;
si(u);si(v);
g[u].PB(v);
g[v].PB(u);
}
queue<int> Q;
Q.push(1);
vis[1]=1;
dist[1]=0;
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i=0;i<SZ(g[u]);i++)
if(!vis[g[u][i]])
{
dist[g[u][i]]=dist[u]+1;
Q.push(g[u][i]);
vis[g[u][i]]=1;
}
}
dout(dist[n]);
for(int i=1;i<=n;i++)
{
g[i].clear();
vis[i]=0;
}
}
return 0;
}