HackerEarth Mittal wants to go to play! problem solution

In this HackerEarth Mittal wants to go to play! problem solution Mittal lives in the Niti Colony. The colony has N houses numbered from 1 to N. There are M bidirectional roads in the colony for travelling between houses. There might be multiple roads between two houses.

Mittal lives in the house with index 1. He has friends in all houses of the colony. He is always wanting to visit them to play. But his mom is really strict. She only allows him to go out for K units of time. This time includes the time taken to go to his friend's house , play with the friend and time taken to come back home.

You are given Q queries. In each query, Mittal wants to go to his friend in house A , given K units of time. Help him find the maximum time that he can play. If K units of time is not sufficient to visit his friend and return back, Mittal will not go and playing time will be zero.

HackerEarth Mittal wants to go to play! problem solution.

#include<bits/stdc++.h>

using namespace std;
 
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define gc getchar_unlocked

vector< vector<pii> >orig;
int n,m;
int dist[100004];
int lim=1000000000;
void dij(int start)
{
      priority_queue<pii,vector<pii>, greater<pii> > Q; 
      for(int i=1;i<=n;i++)
        dist[i]=lim;
     dist[start] = 0;
      Q.push(pii(0,start));
      int cc=0;
      while(!Q.empty()) 
      {
            cc++;
            pii top = Q.top();
            Q.pop();
            int v = top.second, d = top.first;

            if(d <= dist[v]) 
            {
                  for(int i=0;i<orig[v].size();i++){
                        int v2 = orig[v][i].first, cost = orig[v][i].second;
                        if(dist[v2] > dist[v] + cost) 
                        {
                              // update distance if possible
                              dist[v2] = dist[v] + cost;
                              // add the vertex to queue
                              Q.push(pii(dist[v2], v2));

                        }
                  }
            }
            if(cc==n)
            return ;
      }
}

int main()
{
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    int t;
    cin>>t;
    assert(1<=t && t<=10);
    while(t--)
    {
        int i,j,k,x,y,m,c,q;
        cin>>n>>m;
            
        assert(1<=n && n<=10000);
        assert(1<=m && m<=100000);
        orig.clear();
        orig.resize(n+1);
        rep(i,m)
        {
            cin>>x>>y>>c;
            assert(1<=x && x<=n);
            assert(1<=y && y<=n);
            // if(x==y)
            // {
            //     cout<<x<<" "<<y<<"\n";
            // }
            assert(x!=y);
            assert(1<=c && c<=1000);
            orig[x].pb(mp(y,c));
            orig[y].pb(mp(x,c));
        }
        dij(1);
        cin>>q;
        for(i=1;i<=n;i++)
        {
            assert(dist[i]<lim);
        }
        while(q--)
        {
            cin>>x>>k;
            assert(2<=x && x<=n);
            assert(1<=c && c<=10000);
            cout<<max(0,k-2*dist[x]);
            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("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",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 Q = int(1e4)+1;
const int M = int(1e5)+1;
const int T = 10 +1;
const int K = int(1e4) + 1;
const int C = int(1e4)+1;
const int INF = int(2e9);
VII g[N];
int vis[N];
int dist[N];

int main()
{
  int t;si(t);
  assert(t<T);
  while(t--)
  {
    int n,m;
    si(n);si(m);
    assert(n<N);
    assert(m<M);
    for(int i=1;i<=m;i++)
    {
      int u,v,w;
      si(u);si(v);si(w);
      assert(1<=u && u<=n);
      assert(1<=v && v<=n);
      assert(w<C);
      g[u].PB(MP(v,w));
      g[v].PB(MP(u,w));
    }
    set<II> S;
    for(int i=1;i<=n;i++)
      dist[i]=INF;
    dist[1]=0;
    S.insert(MP(0,1));
    while(!S.empty())
    {
      II top = *S.begin();
      S.erase(S.begin());
      int u = top.S;
      if(vis[u])continue;
      vis[u]=1;
      for(int i=0;i<SZ(g[u]);i++)
        if(dist[u]+g[u][i].S<dist[g[u][i].F])
        {
          dist[g[u][i].F]=dist[u]+g[u][i].S;
          S.insert(MP(dist[g[u][i].F],g[u][i].F));
        }
    }
    int q;si(q);
    assert(q<Q);
    while(q--)
    {
      int a,k;
      si(a);si(k);
      assert(1<=a && a<=n);
      assert(k<K);
      dout(max(0,k - 2*dist[a]));
    }
    for(int i=1;i<=n;i++)
    {
      g[i].clear();
      vis[i]=0;
    }
  }
  return 0;
}