3615 -- Cow Hurdles

http://acm.pku.edu.cn/JudgeOnline/problem?id=3615
N 個の駅があり，M 本の一方通行の道が繋いでいて，それぞれの道には高さ H_i のハードルがあるとする．
駅 A_i から駅 B_i まで行くとき，途中で越えなければならないハードルの最大の高さの最小値を出力せよという問題．
もし A_i から B_i までの経路が存在しない場合は -1 を出力する．

いわゆる最短経路問題のひとつ．
複数の駅のペア間の最小値を問われるので，任意の2ノード間の最短経路を求めることができる Warshall-Floyd 法というアルゴリズムで解いた．
http://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB-%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
Wikipedia を見ながら実装．アイデアはシンプルでわかりやすいと思う．

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

vector<vector<int> > floyd(const vector<vector<int> >& g, const vector<vector<int> >& w)
{
  const int N = g.size();
  vector<vector<int> > dist(N+1, vector<int>(N+1, numeric_limits<int>::max()));
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < g[i].size(); j++) {
      const int to = g[i][j];
      dist[i][to] = w[i][j];
    }
  }

  for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= N; j++) {
        dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));
      }
    }
  }
  return dist;
}

int main()
{
  int N, M, T;
  cin >> N >> M >> T;
  vector<vector<int> > g(N+1);
  vector<vector<int> > w(N+1);
  for (int i = 0; i < M; i++) {
    int s, e, h;
    cin >> s >> e >> h;
    g[s].push_back(e);
    w[s].push_back(h);
  }

  const vector<vector<int> > dist = floyd(g, w);
  for (int i = 0; i < T; i++) {
    int a, b;
    cin >> a >> b;
    int c = dist[a][b];
    if (c == numeric_limits<int>::max()) {
      cout << -1 << endl;
    } else {
      cout << c << endl;
    }
  }
  return 0;
}