【Audiophobia UVA - 10048 】【Floyd算法】-白红宇

【Audiophobia UVA - 10048 】【Floyd算法】

阅读量：4966 次

发布时间：2019-06-12

本文共 1209 字，大约阅读时间需要 4 分钟。

题目大意：从a城市到b城市的路径中，尽可能让一路上的最大噪音最小。

题目思路：设d [ i ][ j ]表示 i 到 j 的最大噪音的最小值。那么d [ i ][ j ] = min( d[ i ][ j ] ,max( d [ i ][ k ] , d [ k ][ j ]) );

AC代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                using namespace std;const int maxn = 100 + 100;const int INF = 0x3f3f3f3f;int C, S, Q;int c1, c2, d;int dist[maxn][maxn];void Floyd(){ for(int k = 1; k <= C; k++) { for(int i = 1; i <= C; i++) for(int j = 1; j <= C; j++) dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j])); }}int main(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int cnt = 0; while(cin >> C >> S >> Q && C && S && Q) { ++cnt; for(int i = 1; i <= C; i++) for(int j = 1; j <= C; j++) dist[i][j] = INF; for(int i = 0; i < S; i++) { cin >> c1 >> c2 >> d; dist[c1][c2] = dist[c2][c1] = d; } Floyd(); if(cnt > 1) cout << endl; cout << "Case #" << cnt << endl; for(int i = 0; i < Q; i++) { cin >> c1 >> c2; if(dist[c1][c2] == INF) cout << "no path" << endl; else cout << dist[c1][c2] << endl; } }}