HackerEarth Smart travel agent problem solution YASH PAL, 31 July 202417 February 2026 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 = %lldn", 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("%lldn",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;} coding problems solutions HackerEarth HackerEarth