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