POJ 1797 Heavy Transportation（迪杰斯特拉最短路变形）

传送门

题意分析：Hugo想要扩展他的公司，他有起重机要到目的地，到达目的地有很多条路径，但是，每一条路都有相应承重量，现在需要找出到达目的地的最大承重道路的承重质量。

解题分析：首先，每一条路径的承重量取决于承重量最小的那条道路（短板效应），所以就是找所有路径的最小值，然后选择最小值最大的路径，输出其最小值，这是最短路的变种，需要运用松弛操作，遍历所有路径，记录每条路径的最小值，同时选择同目的地路径最大值。

代码如下

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int mp[1010][1010];
const int maxn = 0x3f3f3f3f;
int main()
{
    int a,t = 0;
    scanf("%d",&a);
    while(a--)
    {
        int b,c,site1,site2,dis,d[1010],v[1010];
        scanf("%d %d",&b,&c);
        memset(v,0,sizeof(v));
        for(int i = 0;i < 1001; i++)
        {
            for(int j = 0;j < 1001; j++)
            {
                mp[i][j] = 0;
            }
        }
        for(int i = 0;i < c; i++)
        {
            scanf("%d %d %d",&site1,&site2,&dis);
            mp[site1][site2] = mp[site2][site1] = dis;
        }
        for(int i = 1;i <= b; i++)
            d[i] = mp[1][i];
        for(int i = 0;i < c; i++)
        {
            int m = 0,x = 0;
            for(int j = 1;j <= b; j++)
            {
                if(m <= d[j] && !v[j])
                {
                    x = j;
                    m = d[j];
                }
            }
            v[x] = 1;
            for(int j = 1;j <= b; j++)
                d[j] = max(d[j],min(d[x],mp[x][j]));
        }
        printf("Scenario #%d:\n%d\n\n",++t,d[b]);
    }
    return 0;
}