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