In this HackerEarth Byteland Trip problem solution Chintu is a member of the Lolympics committee and is assigned the task of dropping the players from the one stadium to another. There are total N stadiums in Byteland. There is at least one path between any two stadiums. Each stadium has a Dominos outlet near it. Chintu loves pizza and will not drive the bus until and unless he gets one when he's hungry. A trip from one stadium to another can be completed by buying atmost X pizzas for Chintu. He eats pizza at the beginning of each trip which is also counted as one of the X pizzas. Calculate the total minimum distance that Chintu can cover after eating a single pizza i.e. the distance after which Chintu gets hungry and throws tantrums.

Chintu can buy at most one pizza from one stadium.


HackerEarth Byteland Trip problem solution


HackerEarth Byteland Trip problem solution.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000000007
#define ll long long int
#define pb push_back
#define mk make_pair
ll power(ll a, ll b) {
ll x = 1, y = a;
while(b > 0) {
if(b%2 == 1) {
x=(x*y);
if(x>mod) x%=mod;
}
y = (y*y);
if(y>mod) y%=mod;
b /= 2;
}
return x;
}
ll dist[102][102];
ll dup[102][102];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
ll n,x,m,u,v,w,i,j,k;
cin>>n>>x>>m;
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
dist[i][j] = mod;
}
dist[i][i] = 0;
}
while(m--) {
cin>>u>>v>>w;
dist[u][v] = dist[v][u] = w;
}
// Floyd Warshall
for(k = 1; k <= n; k++) {
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j],dist[k][j]+dist[i][k]);
}
}
}
ll l,r,mid,res,maxi;
l = 1;
r = mod;
res = 1;
while(l <= r) {
mid = (l+r)/2LL;
maxi = 0LL;
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
dup[i][j] = (dist[i][j]<=mid)?1LL:mod;
}
}
//Floyd Warshall
for(k = 1; k <= n; k++) {
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
dup[i][j] = min(dup[i][j],dup[k][j]+dup[i][k]);
}
}
}
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
maxi = max(maxi,dup[i][j]);
}
}
if(maxi <= x) {
res = mid;
r = mid-1LL;
}
else {
l = mid+1LL;
}
}
cout<<res<<endl;
return 0;
}

Second solution

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <memory.h>
#include <cassert>

using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second

const int N = 111;
const int M = 100500;
const int INF = (int)1e9;

int n, x, m;
int best[N];
long long rem[N];
vector< pair<int, int> > g[N];

bool go(int ver, long long value) {
priority_queue< pair< int, pair<long long, int> > > pq;
for (int i = 1; i <= n; i++) {
best[i] = INF;
rem[i] = 0LL;
}
best[ver] = 0;
pq.push(mp(0, mp(0LL, ver)));
while (!pq.empty()) {
int ver = pq.top().S.S;
long long canGo = pq.top().S.F;
int dist = -pq.top().F;
pq.pop();
if (best[ver] < dist) continue;
if (best[ver] == dist && rem[ver] > canGo) {
continue;
}
for (int i = 0; i < (int)g[ver].size(); i++) {
int to = g[ver][i].F;
int cost = g[ver][i].S;
if (cost <= 1LL * canGo) {
long long new_can = canGo - 1LL * cost;
int new_dist = dist;
if (best[to] > dist) {
best[to] = new_dist;
rem[to] = new_can;
pq.push(mp(-best[to], mp(rem[to], to)));
} else if (best[to] == dist && rem[to] < new_can) {
rem[to] = new_can;
pq.push(mp(-best[to], mp(rem[to], to)));
}
} else {
int new_dist = dist + 1;
long long new_can = canGo + value - 1LL * cost;
if (new_can < 0LL) {
continue;
}
if (best[to] > dist) {
best[to] = new_dist;
rem[to] = new_can;
pq.push(mp(-best[to], mp(rem[to], to)));
} else if (best[to] == dist && rem[to] < new_can) {
rem[to] = new_can;
pq.push(mp(-best[to], mp(rem[to], to)));
}
}
}
}
for (int i = 1; i <= n; i++) if (best[i] > x) return false;
return true;
}

bool can(long long value) {
for (int i = 1; i <= n; i++) if (!go(i, value)) return false;
return true;
}

int main() {
scanf("%d%d%d", &n, &x, &m);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].pb(mp(v, w));
g[v].pb(mp(u, w));
}
long long le = 0LL;
long long ri = (long long)1e15 + 1LL;
can(30LL);
while (le < ri) {
long long mid = (le + ri) / 2LL;
if (can(mid)) {
ri = mid;
} else {
le = mid + 1;
}
}
cout << le << endl;
return 0;
}