题意：给出一个c个点，s条边组成的无向图，求一点到另一点的路径上最大权值最小的路径，输出这个值
可以将这个
d[i][j]=min(d[i][j],d[i][k]+d[k][j])
改成 d[i][j]=min(d[i][j],max(d[i][k],d[k][j]))
即为先找出最大权值的一条边，再从这些边中找出最小的
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 #define mod=1e9+7; 12 using namespace std; 13 14 typedef long long LL; 15 const int INF = 0x7fffffff; 16 const int maxn=110; 17 int d[maxn][maxn]; 18 19 int main(){ 20 int n,m,q,i,j,k,kase=0,u,v,w; 21 while(scanf("%d %d %d",&n,&m,&q)!=EOF&&n&&m&&q){ 22 23 for(i=1;i<=n;i++){ 24 for(j=1;j<=n;j++){ 25 if(i==j) d[i][j]=0; 26 else d[i][j]=INF; 27 } 28 } 29 for(i=1;i<=m;i++){ 30 scanf("%d %d %d",&u,&v,&w); 31 d[u][v]=w;//无 向图，所以两个方向都赋上权值 32 d[v][u]=w; 33 } 34 35 for(k=1;k<=n;k++) 36 for(i=1;i<=n;i++) 37 for(j=1;j<=n;j++) 38 d[i][j]=min(d[i][j],max(d[i][k],d[k][j])); 39 40 if(kase) printf(" "); 41 printf("Case #%d ",++kase); 42 while(q--){ 43 int x,y; 44 scanf("%d %d",&x,&y); 45 46 if(d[x][y]!=INF) printf("%d ",d[x][y]); 47 else printf("no path "); 48 } 49 } 50 return 0; 51 }