题目链接poj1797
我们可以用dilkstra算法,由于是求最大的货物重量,我们将dis[N]数组的最小min,改为求最大,然后比较max(dis[i],min(dis[v],e[v][i])),根据上式求出来的结果,即为我们所求答案.
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#define N 1100
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int e[N][N],book[N],dis[N];
int cnt=1;
void d()
{
memset(book,0,sizeof(book));for(int i=1;i<=n;i++)dis[i] = e[1][i];book[1] = 1;for(int i=1;i<=n-1;i++){
int p;int maxx=0;for(int j=1;j<=n;j++)if(book[j]==0&&dis[j]>maxx){
maxx = dis[j];p = j;}book[p] = 1;for(int j=1;j<=n;j++)dis[j] = max(dis[j],min(dis[p],e[p][j]));}}int main()
{
int k;cin>>k;while(k--){
cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)e[i][j]=0;for(int i=1;i<=m;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);if(z>e[x][y])e[x][y]=e[y][x]=z;}d();cout<<"Scenario #"<<cnt++<<":"<<endl;cout<<dis[n]<<endl<<endl;}
}