HackerEarth Monk and the Islands problem solution YASH PAL, 31 July 2024 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_backint 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;} coding problems