HackerEarth Monk and the Islands problem solution

by
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

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;
}