题目链接

题意：给出n个城镇，m条路径，路径上会有噪音，给出起点和终点，问从起点到终点的所有路径中受到的噪音最大值最小的数。

solution： Floyed 把 “+” 改为 “max”

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100 + 7;
#define Inf 0x3f3f3f3f
int a[N][N];
int n, m, e;
int main(){int ka=0;while( ~scanf("%d%d%d", &n, &m, &e ) && ( n||m||e ) ){if( ka ) cout<<"\n";printf("Case #%d\n", ++ka);for ( int i=1; i<=n; i++ )for ( int j=1; j<=n; j++ ) if(i!=j) a[i][j]=Inf;else a[i][j]=0;for ( int i=1; i<=m; i++ ){int u, v, w;cin>>u>>v>>w;a[u][v]=a[v][u]=w;}for ( int k=1; k<=n; k++ )for ( int i=1; i<=n; i++ )for ( int j=1; j<=n; j++ )a[i][j]=min(a[i][j], max(a[i][k], a[k][j]) );while( e-- ){int x, y;cin>>x>>y;if( a[x][y] < Inf ) printf("%d\n", a[x][y] ); else printf("no path\n");}}
}