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


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