HackerEarth Smart travel agent problem solution

In this HackerEarth Smart travel agent problem solution Our smart travel agent, Mr. X's current assignment is to show a group of tourists a distant city. As in all countries, certain pairs of cities are connected by two-way roads. Each pair of neighboring cities has a bus service that runs only between those two cities and uses the road that directly connects them. Each bus service has a particular limit on the maximum number of passengers it can carry. Mr. X has a map showing the cities and the roads connecting them, as well as the service limit for each bus service.

It is not always possible for him to take all tourists to the destination city in a single trip. For example, consider the following road map of seven cities, where the edges represent roads and the number written on each edge indicates the passenger limit of the associated bus service.

What is the best way for Mr. X to take all tourists to the destination city in the minimum number of trips?

HackerEarth Smart travel agent problem solution.

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 100005
#define pii pair< long long int,long long  int >
#define pb(x) push_back(x)
long long int INF=1000000000000000;
struct comp {
    bool operator() (const pii &a, const pii &b) {
        return a.second > b.second;
    }
};
priority_queue< pii, vector< pii >, comp > Q;
vector< pii > G[MAX];
long long int D[MAX];
bool F[MAX];
int Path[MAX];
vector<int> p;
vector<int> p1;
int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        long long int Dist=0;
        int i, u, v, w, sz, nodes, edges, starting;
        // create graph
        scanf("%d %d", &nodes, &edges);
        for(i=0; i<edges; i++) {
            scanf("%d %d %d", &u, &v, &w);
            G[u].pb(pii(v, w));
            G[v].pb(pii(u, w)); // for undirected
        }
        int A,B,C;
        scanf("%d%d%d", &A,&B,&C);
        // initialize graph
        /*
        From A to B
        */
        for(i=1; i<=nodes; i++){ 
            D[i] = INF;
            F[i]=false;
        }
        D[A] = 0;
        Q.push(pii(A, 0));

        // dijkstra
        while(!Q.empty()) {
            u = Q.top().first;
            Q.pop();
            if(F[u]) continue;
            sz = G[u].size();
            for(i=0; i<sz; i++) {
                v = G[u][i].first;
                w = G[u][i].second;
                if(!F[v] && D[u]+w < D[v]) {
                    D[v] = D[u] + w;
                    Path[v]=u;
                    //printf("%d %d-->\n",v,u);
                    Q.push(pii(v, D[v]));
                }
            }
            F[u] = 1; // done with u
        }
        //IF distance from A to B is INF
        if(D[B]==INF)
        {
            printf("No Train Found.\n");
            goto end;
        }
        else
        {
            Dist+=D[B];
            //Restore path
            for (int v=B; v!=A;v=Path[v])
            {
                p.push_back(v);
            }
            p.push_back(A);
        }
        // result
        //for(i=1;i<=nodes; i++) printf("Node %d, min weight = %lld\n", i, D[i]);
        /*
        From B to C
        */
        Q=priority_queue< pii, vector< pii >, comp > ();
        for(i=1; i<=nodes; i++)
        { 
            D[i] = INF;
            F[i]=false;
        }
        D[B] = 0;
        Q.push(pii(B, 0));
        // dijkstra
        while(!Q.empty()) 
        {
            u = Q.top().first;
            Q.pop();
            if(F[u]) continue;
            sz = G[u].size();
            for(i=0; i<sz; i++) 
            {
                v = G[u][i].first;
                w = G[u][i].second;
                if(!F[v] && D[u]+w < D[v]) {
                    D[v] = D[u] + w;
                    Path[v]=u;
                    Q.push(pii(v, D[v]));
                }
            }
            F[u] = 1; // done with u
        }    

        //Check there is path or not
        if(D[C]==INF)
        {
            printf("No Train Found.\n");
            goto end;
        }
        else
        {
            Dist+=D[C];
            printf("%lld\n",Dist);
            for(i=p.size()-1;i>=0;i--)
                printf("%d ",p[i]);
            p.clear();
            for (int v=C; v!=B; v=Path[v])
                p.push_back(v);
            for(i=p.size()-1;i>=0;i--)
                printf("%d ",p[i]);    
            printf("\n");          
        }
        end:
        //Clear Graph
        p.clear();
        for(i=0;i<MAX;i++)
            G[i].clear();
        Q=priority_queue< pii, vector< pii >, comp > ();

    }
    return 0;
}#include<bits/stdc++.h>
using namespace std;
#define MAX 1000010
 
vector < pair < int , int > > v[MAX];
int par[MAX],vis[MAX],n,m,start,dest,tour;
 
 
void dfs(int i,int mid)
{
  vis[i]=1;
  int siz=v[i].size();
  for(int j=0;j<siz;j++)
  {
    if(vis[v[i][j].second]==0&&v[i][j].first>=mid)
    {
      dfs(v[i][j].second,mid);
      par[v[i][j].second]=i;
    }
  }
  
}
 
 
int solve(int mid)
{   
 memset(vis,0, sizeof vis);
  par[start]=start;
  dfs(start,mid);
  int check=0;
  for(int i=0;i<n;i++)
  {
    if(vis[i]==0)
    {
      check=1;
      break;
    }
  }
  
  if(check==1)
  return 0;
  return 1;
}
 
void find(int i)
{
  if(i==par[i])
    {
  printf("%d ",i+1);
  return;
    }
  find(par[i]);
  printf("%d ",i+1);
}
 
int main()
{
  scanf("%d %d",&n,&m);
  int x,y,d,mini=0,maxi=MAX;
  for(int i=0;i<m;i++)
  {
  scanf("%d %d %d",&x,&y,&d);
  x--;
  y--;
  v[x].push_back(make_pair(d,y));
  v[y].push_back(make_pair(d,x));
  maxi=max(d,maxi);
  mini=min(mini,d);
  }
  scanf("%d %d %d",&start,&dest,&tour);
  start--;
  dest--;
  for(int i=0;i<n;i++)
  sort(v[i].begin(),v[i].end());
  int low=mini,high=maxi,mid;
  while(low<high)
  {
    mid=(low+high+1)/2;
    if(solve(mid))
    low=mid;
    else
    high=mid-1;
  }
  find(dest);
  int ans=tour/(low-1);
  if(tour%(low-1)>0)
  ans++;
  
  
  printf("\n%d",ans);
        
return 0;
}