POJ - 1797 Heavy Transportation （最短路）

74 阅读 0 评论 49 点赞

我是靠谱客的博主喜悦星月，最近开发中收集的这篇文章主要介绍POJ - 1797 Heavy Transportation （最短路），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Background
Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.
Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know.

Problem
You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo’s place) to crossing n (the customer’s place). You may assume that there is at least one path. All streets can be travelled in both directions.
Input
The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings.
Output
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that Hugo can transport to the customer. Terminate the output for the scenario with a blank line.
Sample Input
1
3 3
1 2 3
1 3 4
2 3 5
Sample Output
Scenario #1:
4
问题链接：http://poj.org/problem?id=1797
问题简述：有n座城镇，m条道路，求从城镇1到n的可能最大负重
问题分析：用dijkstra实现，核心方程：（先获取从1到n之间的路取限制重量的最小值，再获取所有可能从1到n之间方法的最大负重）
int g;
g=min(lowb[flag],map[flag][j]);
lowb[j]=max(g,lowb[j]);
代码及注释以下
AC通过的C++语言程序如下：

#include <iostream>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <climits>
#include <iomanip>
#include <queue>
#include<vector>
using namespace std;
const int maxn=99999999;
const int N=1005;
int map[N][N],lowb[N];//存地图以及1到各个点的负重上限
int n,a,b;//n：例子数量，a：城镇数量，b：道路数量
bool vis[N];//城镇的访问标记
int dijk()
{
for(int i=1;i<=a;i++)//重置1到i的负重上限
{
lowb[i]=map[1][i];
}
for(int i=1;i<=a;i++)
{
int flag;//前驱节点
int maxx=0;//存储到前驱节点的最大负重
for(int j=1;j<=a;j++)//从找到最大负重的点开始
{
if(vis[j]!=1&&lowb[j]>maxx)//该点没有访问过
{
maxx=lowb[j];
flag=j;//记录前驱节点
}
}
vis[flag]=1;//标记
for(int j=1;j<=a;j++)
{
if(map[flag][j]!=0)//前驱节点到j点之间有道路
{
int g;//1到前驱节点与前驱节点到j点之间取最小负重
g=min(lowb[flag],map[flag][j]);
lowb[j]=max(g,lowb[j]);//找到每条1到j之间可能的最大负重
}
}
}
return lowb[a];//返回1到a可能的最大负重
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
memset(lowb,0,sizeof(lowb));//初始化
cin>>a>>b;
while(b--)
{
int u,v,w;
cin>>u>>v>>w;
map[u][v]=map[v][u]=w;
}
lowb[1]=0;//1到自身为0
cout<<"Scenario #"<<i<<":"<<endl;
cout<<dijk()<<endl;
cout<<endl;//注意输出格式
//cout<<dis[a]<<endl;
}
return 0;
}