USACO 2.4 Cow Tours

This problem asks about the longest paths among the shortest paths. The basic idea is to use a brutal force search against all pair shortest paths. There are two cases for the shortest paths:

• The shortest path is one of those that’s connecting two pastures that’s already connected. These paths are already available in original graph.
• The shortest path does not exist in original graph. Between two disconnected pastures, say pasture A and pasture B, we can have them connected by having a path go between A and B. Now before we connect A and B, there must exist pasture C and D, such that distance AC is the maximized possible distance between A and all other pastures A already connected in original graph, and similarly distance BD is maximized possible distance between B and all other pastures B already connected in original graph. The new possible longest path of all shortest path between pairs is now distance(AC) + distance(BD) + distance (AB).
• Combining two cases, we can do a brutal force search and find the maximum path.
• For all pastures that have already connected, use Floyd all pair shortest paths to calculate the path values.
• There is no need to explicitly calculate the strongly connected component that connected pastures form, because we would iterate through pair of pastures, rather than through pair of strongly connected components formed by pastures. And we can tell if two pastures needs to be checked because we will only check those that have initial distance value of infinite (meaning not connected initially.).

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <limits>
#include <iomanip>

using namespace std;
#define DOUBLE_MAX std::numeric_limits<double>::max()

int N;

typedef struct Point {
  int x; int y;
} tPoint;

vector<tPoint> points;
vector<vector<double>> dist;
vector<double> dmax;

double distance(int x1, int y1, int x2, int y2) {
  return sqrt((double)pow(x1 - x2, 2) + (double)pow(y1 - y2, 2));
}

int main() {
  ifstream fin("cowtour.in");
  ofstream fout("cowtour.out");

  fin >> N;
  points = vector<tPoint>(N, tPoint());
  dist = vector<vector<double>>(N, vector<double>(N, 0));
  dmax = vector<double>(N, 0);

  for (int i = 0; i < N; ++i) {
    fin >> points[i].x;
    fin >> points[i].y;
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      char c;
      fin >> c;
      if (c == '0') {
        dist[i][j] = DOUBLE_MAX;
      } else {
        dist[i][j] = distance(points[i].x, points[i].y, points[j].x, points[j].y);
      }
    }
  }

  // Flyod all pair shortest path.
  for (int k = 0; k < N; ++k) {
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if ((dist[i][k] + dist[k][j] < dist[i][j]) &&
             dist[i][k] != DOUBLE_MAX &&
             dist[k][j] != DOUBLE_MAX) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  for(int i = 0; i < N; ++i){
    dist[i][i] = DOUBLE_MAX;
  }

  double max_distance = 0;
  for(int i = 0; i < N; ++i){
    double cmax = 0;
    for(int j = 0; j < N; ++j){
      if (dist[i][j] == DOUBLE_MAX)
        continue;
      cmax = std::max(cmax, dist[i][j]);
    }
    dmax[i] = cmax;
    max_distance = std::max(max_distance, cmax);
  }


  double ret = DOUBLE_MAX;
  for(int i = 0; i < N - 1; ++i){
    for(int j = i + 1; j < N; ++j){
      if (i != j && dist[i][j] == DOUBLE_MAX) {
        double d = distance(points[i].x, points[i].y,
                            points[j].x, points[j].y);
        ret = std::min(ret, d + dmax[i] + dmax[j]);
      }
    }
  }

  fout << setiosflags(ios::fixed) << setprecision(6)
    << (max_distance > ret ? max_distance : ret) << endl;

  cout << setiosflags(ios::fixed) << setprecision(6)
  << (max_distance > ret ? max_distance : ret) << endl;
  return 0;
}