放一下他在洛谷的链接：https://www.luogu.org/problemnew/show/UVA10048
第一次见到这道（坑）题是在刘汝佳的紫书（《算法竞赛入门经典》）上，为什么说这道题坑呢？因为这道题刘汝佳弄错了！！！
思路很简单，数据范围很小，所以可以使用Floyd算法的变形：对于从i到j的路径，枚举一个中间点k，假设d[i][j]存储i到j路径上的最大边权的最小值，那么max(d[i][k],d[k][j])就是从i到j，经过k的路径上的最大边权，这可能是一个答案，只需把d[i][j]更新成min(d[i][j],max(d[i][k],d[k][j]))就可以了。而紫书中印成了d[i][j]=max(d[i][j],min(d[i][k],d[k][j]))。这道题还有一个坑点，或者说两个，他是英文题不怪他，但输出格式那么严格就不太好了吧！千万要注意看清格式（其实主要是看不懂英文）。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=105,inf=0x3f3f3f3f; 6 int c,s,q,t=1,G[maxn][maxn]; //数据范围很小，邻接矩阵就可以 7 void floyd() { 8 for(int k=1;k<=c;++k) 9 for(int i=1;i<=c;++i) 10 for(int j=1;j<=c;++j) 11 G[i][j]=min(G[i][j],max(G[i][k],G[k][j])); 12 } 13 int main() { 14 while(scanf("%d%d%d",&c,&s,&q)) { 15 if(!c&&!s&&!q) break; 16 memset(G,inf,sizeof(G)); //每组数据都要更新 17 int u,v,w; 18 for(int i=1;i<=s;++i) { 19 scanf("%d%d%d",&u,&v,&w); 20 G[u][v]=G[v][u]=w; //无向图（废话） 21 } 22 floyd(); 23 if(t!=1) putchar(‘\n‘); //注意输出格式 24 printf("Case #%d\n",t); 25 ++t; 26 for(int i=1;i<=q;++i) { 27 scanf("%d%d",&u,&v); 28 if(G[u][v]==inf) printf("no path\n"); //特判不连通的情况 29 else printf("%d\n",G[u][v]); 30 } 31 } 32 return 0; 33 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9541305.html
