| Time Limit: 3000MS | Memory Limit: 30000K | |
| Total Submissions: 21632 | Accepted: 5754 |
Description
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
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 scenario with a blank line.
Sample Input
1 3 3 1 2 3 1 3 4 2 3 5
Sample Output
Scenario #1: 4
题目大意：
首先输入n个城市，m条街道，然后输入每两个城市之间的最大载容量，判断从1号城市到n号城市的最大载容量是多少的问题。因为要从1号城市往n号城市派一辆汽车过去，当然要满足汽车的载重最大了，但是每条街道又有自己的载容量限制，所以我们只需要对于Dijkstra()稍作一些修改就好。
解题思路：
在Dijkstra()算法中，以前求得的是最短路，判断的条件是:
if ( book[j] == 0 && dis[j] < _min )
{
_min = dis[j];
u = j;
}
这里需要把_min改成_max。。。而max的值为-1.在init（）的过程中，也只需在开始的时候将edge[i][j]改为全部为0的了。。。
还有一处需要改动的地方，就是在进行边的松弛的过程中，我们要做到的是 if ( book[v]==0&&dis[v] < min( dis[u],edge[u][v]) )
代码：
# include<cstdio>
# include<iostream>
using namespace std;
# define MAX 1234
int edge[MAX][MAX];
int book[MAX];
int dis[MAX];
int n,m;
int u,v;
void init()
{
for ( int i = 1;i <= n;i++ )
{
for ( int j = 1;j <= n;j++ )
{
edge[i][j] = 0;
}
}
}
void input()
{
for ( int i = 1;i <= m;i++ )
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
edge[t1][t2] = t3;
edge[t2][t1] = t3;
}
}
int Dijkstra()
{
for ( int i = 1;i <= n;i++ )
{
book[i] = 0;
dis[i] = edge[1][i];
}
int _max;
book[1] = 1;
for ( int i = 1;i <= n-1;i++ )
{
_max = -1;
for ( int j = 1;j <= n;j++ )
{
if ( book[j]==0&&dis[j] > _max )
{
_max = dis[j];
u = j;
}
}
book[u] = 1;
for ( v = 1;v <= n;v++ )
{
if ( book[v]==0&&dis[v] < min( dis[u],edge[u][v]) )
{
dis[v] = min( dis[u],edge[u][v] );
}
}
}
return dis[n];
}
int main(void)
{
int t;cin>>t;
int icase = 1;
while ( t-- )
{
cin>>n>>m;
init();
input();
printf("Scenario #%d:\n",icase++);
printf("%d\n\n",Dijkstra());
}
return 0;
}