Analysis: Vacation Planning by Fatih Gelgi

The problem asks to find the minimum cost for each trip request from a_i to b_i through at least one of the hubs. In this case, computing all shortest path pairs using Floyd-Warshall algorithm will be sufficient for us (note that, N<=200 hence O(N^3) running time is fast enough for the problem).Then the answer of a minimum cost request (a_i,b_i) will be min_x {mincost[a_i,x] + mincost[x,b_i]} where x is a hub and mincost is the distance matrix obtained by Floyd-Warshall.A sample solution is provided as follows:

```#include <fstream>
#include <algorithm>

#define MAX 201
#define INF 1000000000

using namespace std;

int n,m,k,q,mat[MAX][MAX],cnt;
long long sum;

int main()
{
ifstream fin("vacation.in");
fin >> n >> m >> k >> q;

for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
if (i!=j) mat[i][j]=INF;

int u,v,d;
for (int i=0; i<m; i++)
{
fin >> u >> v >> d;
mat[--u][--v]=d;
}

// Floyd-Warshall
for (int x=0; x<n; x++)
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
mat[i][j]=min(mat[i][j],mat[i][x]+mat[x][j]);

for (int i=0; i<q; i++)
{
fin >> u >> v;
int cost=INF;
for (int j=0; j<k; j++)
cost=min(cost,mat[u-1][j]+mat[j][v-1]);
if (cost!=INF) cnt++,sum+=cost;
}

fin.close();

ofstream fout("vacation.out");
fout << cnt << "\n" << sum << "\n";
fout.close();
}
```