首页 > 代码库 > POJ2263&ZOJ1952--Heavy Cargo【Floyd】多源最短路变形

POJ2263&ZOJ1952--Heavy Cargo【Floyd】多源最短路变形

链接:http://poj.org/problem?id=2263

题意:有n个点,m条路,每条路双向的,现在卡车从某点到另一点,卡车的承载无上限,但是马路的承载有上限,问卡车应该承载多少才不会压坏马路。


poj2253和它类似,链接:http://poj.org/problem?id=2253
解题报告:Here


就是在两点之间找一条路径,使路径中权值最小的那条边的权值最大,edge数组记录当前路径中最小权值边的权值

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 510
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson r,m+1,rt<<1|1

map<string,int>mp;
int edge[MAXN][MAXN];
int n,m,cnt;
void floyd(){
    int i,j,k;
    for(k=1;k<=cnt;k++){
        for(i=1;i<=cnt;i++){
            for(j=1;j<=cnt;j++){
                edge[i][j] = max(edge[i][j],min(edge[i][k],edge[k][j]));
            }
        }
    }
}
int main(){
    int k = 1,i,x;
    string str1,str2;
    while(scanf("%d%d",&n,&m),n||m){
        if(!mp.empty()) mp.clear();
        cnt = 0;
        memset(edge,0,sizeof(edge));
        for(i=0;i<m;i++){
            cin>>str1>>str2>>x;
            if(!mp[str1])   mp[str1] = ++cnt;
            if(!mp[str2])   mp[str2] = ++cnt;
            edge[mp[str1]][mp[str2]] = edge[mp[str2]][mp[str1]] = x;
        }
        floyd();
        cin>>str1>>str2;
        printf("Scenario #%d\n",k++);
        printf("%d tons\n\n",edge[mp[str1]][mp[str2]]);
    }
    return 0;
}