The Max Weight
Time Limit: 1000 ms Memory Limit: 64 MB
Total Submission: 36 Accepted: 4
Description
There a lot of bridges connect different positions in Venice,but they can't carry too much weigh,so each of them has a limit which can be described as an interger.A man wants to carry some goods from positon 1 to n.Help him find how much can he carry.
Input
There are T cases.
For each case,the number of positions ( 1 < = n < = 100) and number m of bridges are exhibited on the first line.The following m lines contain triples of integers specifying start and end positions of the bridge and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one bridge between each pair of crossings.
Output
The output for every scenario begins with a line containing "Case #i:", where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that the man can transport. Terminate the output for the scenario with a blank line.
Sampel Input
1
3 3
1 2 3
1 3 4
2 3 5
Sample Output
題意：
n個點(diǎn)，有些點(diǎn)間有橋，橋上有最大承重量，問你從1到n可以最大攜帶的物品的重量。
題解：
Folyd算法變形，把求最短路徑的和改為求最大載重量的問題，關(guān)鍵是dis[i][j]=dis[i][j]>dis[i][k]+dis[k][j]?dis[i][j]>dis[i][k]+dis[k][j]?:dis[i][j];換成dis[i][j]
=max(dis[i][j],min(dis[i][k],dis[k][j]));
1
#include<iostream>
2#include<cmath>
3#include<string.h>
4using namespace std;
5long long dis[105][105];
6
8void Floyd(int n)
9
{
10
for(int k=1; k<=n; k++)
11 for(int i=1; i<=n; i++)
12 for(int j=1; j<=n; j++)
13
{
14 if(i!=k&&j!=k&&dis[i][k]&&dis[k][j])
15 dis[i][j]=max(dis[i][j],min(dis[i][k],dis[k][j]));
16
}
17
}
18
19int main()
20{
21 int t,i,j,m,n;
22 cin>>t;
23 for(int k=1; k<=t; k++)
24 {
25 cin>>n>>m;
26 memset(dis,0,sizeof (dis));
27 i=1;
28 for(int s,e,w; i<=m; i++)
29 {
30 cin>>s>>e>>w;
31 dis[s][e]=dis[e][s]=w;
32 }
33
34 Floyd(n);
35
36 cout<<"Case #"<<k<<':'<<endl<<dis[1][n]<<endl<<endl;
37 }
38 return 0;
39}