这道题要使游客从一个点到另一个点，求最小的趟数，我们用floyd算法将所有路径中的最小边的

最大值求出来，然后用计算trips就行了。求最小边的最大值的方程为：

d[i][j]=max{d[i][j],min{d[i][k],d[k][j]}}

初始化:所有 d[i][j]=0;

 

#include
     
       #define MAXD 110 int u, v, w, S, D, T, R, N; int d[MAXD][MAXD]; int min( int a, int b) {
   return a < b ? a : b; } void init() {
   for( int i = 1; i <= N; i ++) for( int j = 1; j <= N; j ++)             d[i][j] = 0; for( int i = 1; i <= R; i ++)     {
           scanf( "%d%d%d", &u ,&v, &w);         d[u][v] = d[v][u] = w;     } } void floyd() {
   for( int k = 1; k <= N; k ++) for( int i = 1; i <= N; i ++) for( int j = 1; j <= N; j ++) if( min(d[i][k], d[k][j]) > d[i][j])                     d[i][j] =  min( d[i][k], d[k][j]); } int main() {
   int cas = 0; while( true)     {
           scanf( "%d%d", &N, &R); if( N == 0 && R == 0) break;         init();         floyd();         scanf( "%d%d%d", &S, &D, &T); int ans;         ans = T / (d[S][D] - 1); if( T % (d[S][D] - 1) != 0)         ans++;         printf("Scenario #%d\n", ++cas);         printf("Minimum Number of Trips = %d\n", ans);         printf("\n");     } return 0; }