这道题是Floyd的变形
改成d[i][j] = min(d[i][j], max(d[i][k], d[k][j]))就好了。
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
int d[MAXN][MAXN], n, m, q;int main()
{int kase = 0;while(~scanf("%d%d%d", &n, &m, &q) && n){REP(i, 0, n)REP(j, 0, n)d[i][j] = (i == j ? 0 : 1e9);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);u--; v--;d[v][u] = d[u][v] = min(d[u][v], w);}REP(k, 0, n)REP(i, 0, n)REP(j, 0, n)d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));if(kase) puts("");printf("Case #%d\n", ++kase);while(q--){int u, v;scanf("%d%d", &u, &v);u--; v--;if(d[u][v] == 1e9) puts("no path");else printf("%d\n", d[u][v]);} }return 0;
}