UVA 10048 - Audiophobia

题目大意：给定一个无向图加权图，求给定的两点间可经过的路径的最大边权最小。

题目分析：这是Floyd算法的变形，设d[i][j]:表示从i到j所经过的最大权值的最小值

状态转移方程：d[i][j]=min{max{d[i][k],d[k][j]},d[i][j]},利用Floyd算法改

变状态转移部分的代码即可AC。

//Uva  10048 - Audiophobia
//多源最短路的变形
//d[i][j]:表示从i到j所经过的最大权值的最小值
//状态转移方程：d[i][j]=min{max{d[i][k],d[k][j]},d[i][j]},要求(i,k),(k,j)存在
#include <iostream>
#include <memory.h>
#include <cstdio>
#define INF  200000000
using namespace std;
const int maxn=110;
int c,s,q;//分别表示顶点数、边数及询问数
int cost[maxn][maxn];
int d[maxn][maxn];
int main()
{
    int count=0;
    bool flag=false;
    while(cin>>c>>s>>q,c||s||q)
    {
        if(flag)    cout<<endl;
        else    flag=true;
        int u,v,w;
        count++;
        memset(cost,-1,sizeof(cost));
        for(int i=0;i<s;i++)
        {
            cin>>u>>v>>w;
            u--,v--;
            cost[v][u]=w;
            cost[u][v]=w;
        }
        for(int i=0;i<c;i++)
        for(int j=0;j<c;j++)
        {
            if(cost[i][j]==-1)  cost[i][j]=INF;
            d[i][j]=cost[i][j];
        }
        for(int k=0;k<c;k++)
        for(int i=0;i<c;i++)
        for(int j=0;j<c;j++)
        {
            d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
        }
        printf("Case #%d\n",count);
        for(int i=0;i<q;i++)
        {
            cin>>u>>v;
            u--,v--;
            if(d[u][v]!=INF)     cout<<d[u][v]<<endl;
            else                cout<<"no path"<<endl;
        }
    }
    return 0;
}