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.

`#include <bits/stdc++.h>using namespace std;#define mod 1000000000007#define ll long long int#define pb push_back#define mk make_pairll 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;ll dup;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 secondconst 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;}`