「Bzoj 1641」「Usaco2007 Nov」Cow Hurdles 奶牛跨栏 (最短路)

BZOJ 1641
Luogu 2888
from: USACO 2007 Nov Sliver(USACO刷题第15题)

最大值最小，第一反应二分。
但是这题把样例化画出来以后发现可以用最短路跑，改一下松弛为
$$G[i][j] = min(G[i][j], max(G[i][k], G[k][j]))$$
数据小Floyd水过。
注意邻接矩阵重边问题！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;

const int MAXN = 300 + 5, INF = 1000000000;

int n, m, t, G[MAXN][MAXN];

void clean() {
    for (int i=0;i<=n;i++)
    for (int j=0;j<=n;j++) G[i][j] = INF;
}
void init() {
    clean();
    for (int i=1;i<=m;i++) {
        int si, ei, hi;
        scanf("%d%d%d", &si, &ei, &hi);
        G[si][ei] = min(G[si][ei], hi);//重边 
    }
}
void solve() {
    for (int k=1;k<=n;k++)
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++) 
    if (i!=j&&i!=k&&j!=k&&G[i][k]!=INF&&G[k][j]!=INF) G[i][j] = min(G[i][j], max(G[i][k], G[k][j]));
    for (int i=1;i<=t;i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (G[a][b]!=INF) printf("%d\n", G[a][b]); else printf("-1\n");
    }
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d%d", &n, &m, &t)==3) init(), solve();
    return 0;
}