POJ 3615 Cow Hurdles（最短路径Floyd算法）

最短路径Floyd算法
题目意思：
n个点，m条有向边， 每条边都有一个长度。 从点x 到 点y，有一条路径的话，最长的那一段距离表示这条路径的花费。
求任意两点之间的最小花费。
本题要点：
1、n <= 300, 可以用 floyd 算法，求任意两点之间的最小花费。
原来的路径是累加起来的，现在只需要记录，这条路径的最大长度即可。
2、 点 i 经过 点 k ，然后到达点 j. 那么，d[i][j] = min(d[i][j], max(d[i][k], d[k][j])),
前提是， i 和 k 点必须连通的， k 和 j 点也是必须连通的(d[i][k] < INF， d[k][j] < INF)。
不然 max(d[i][k], d[k][j]) == INF ,求出来 d[i][j] == INF, 如果 i 和 j 原来是连通的，就出错了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 310, INF = 0x7fffffff;
int d[MaxN][MaxN];
int n, m, query;void floyd()
{
    for(int k = 1; k <= n; ++k){
    for(int i = 1; i <= n; ++i){
    if(d[i][k] < INF)for(int j = 1; j <= n; ++j){
    if(d[k][j] < INF){
    int tmp = max(d[i][k], d[k][j]);if(d[i][j] > tmp){
    d[i][j] = tmp;}}}}}
}int main()
{
    int x, y, z;scanf("%d%d%d", &n, &m, &query);for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)d[i][j] = INF;for(int i = 1; i <= m; ++i){
    scanf("%d%d%d", &x, &y, &z);d[x][y] = z;}floyd();for(int i = 0; i < query; ++i){
    scanf("%d%d", &x, &y);if(d[x][y] == INF){
    printf("-1\n");}else{
    printf("%d\n", d[x][y]);}}return 0;
}/* 5 6 3 1 2 12 3 2 8 1 3 5 2 5 3 3 4 4 2 4 8 3 4 1 2 5 1 *//* 4 8 -1 */