题目链接戳这里
题意：给出一张图，求出从一点到另一点经过的最大权值的最小值
一遍弗洛伊德即可。 map[i][j]=min(map[i][j],max(map[i][k],map[k][j]))
注意是无向图 注意变态的输出方式
代码
#include<stdio.h> #include<string.h> #include<queue> #include<iostream> #include<algorithm> using namespace std; //弗洛伊德 const int maxn=105; const int INF=0x3f3f3f3f; int map[maxn][maxn]; int main() { int C,S,Q; int casen=0; while(~scanf("%d%d%d",&C,&S,&Q)&&C&&S&&Q) { for(int i=1; i<=C; i++) for(int j=1; j<=C; j++) map[i][j]=INF; while(S--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(map[u][v]>w) { map[u][v]=w; map[v][u]=w;//注意是无向图 } } for(int k=1; k<=C; k++) for(int i=1; i<=C; i++) for(int j=1; j<=C; j++) if(map[i][j]>max(map[i][k],map[k][j])) map[i][j]=max(map[i][k],map[k][j]); if(casen)//万恶的PE printf("\n"); printf("Case #%d\n",++casen); while(Q--) { int u,v; scanf("%d%d",&u,&v); map[u][v]==INF?printf("no path\n"):printf("%d\n",map[u][v]); } } return 0; }