USACO 2.4 Bessie Come Home

Pretty straightforward solution with Floyd all pair shortest path algorithm: we simply compute every path and pick up the shortest one between a cow and the barn. One catch is to prepare all the input data. In particular, there is test data where for same pair of pastures, say A and B, distance between AB and BA is different. So need a check to select the smaller one, if distance AB and BA is different. This is very annoying, though it sounds legitimate test data, and maybe intentionally crafted in such a way.

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

using namespace std;

int N;
vector<vector<int>> dist(52, vector<int>(52, INT_MAX));

int char2index(char c) {
  if (c >= 'a') {
    return c - 'a' + 26;
  }
  return c - 'A';
}

int main() {
  ifstream fin("comehome.in");
  ofstream fout("comehome.out");
  
  fin >> N;
  for (int i = 0; i < N; ++i) {
    char c1, c2; int d;
    fin >> c1 >> c2 >> d;
    int m = char2index(c1), n = char2index(c2);
    if (d < dist[m][n]) {
        // Need this check because sometimes dist[m][n]
        // read from input does not equal to dist[n][m]!!
        dist[m][n] = d; dist[n][m] = d;
    }
  }
  
  for (int k = 0; k < 52; ++k) {
    for (int i = 0; i < 52; ++i) {
      for (int j = 0; j < 52; ++j) {
        if (dist[i][k] + dist[k][j] < dist[i][j] &&
            dist[i][k] != INT_MAX &&
            dist[k][j] != INT_MAX) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  
  for (int i = 0; i < 52; ++i) {
    dist[i][i] = INT_MAX;
  }
  
  int ret = INT_MAX; int index = 0;
  for (int i = 0; i < 26; ++i) {
    if (dist[i][25] == INT_MAX)
        continue;
    if (ret > dist[i][25]) {
        ret = dist[i][25];
        index = i;
    }
  }
  
  cout << (char)('A' + index) << " " << ret << endl;
  fout << (char)('A' + index) << " " << ret << endl;
}