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个点，有些点间有桥，桥上有最大承重量，问你从1到n可以最大携带的物品的重量。
题解：
Folyd算法变形，把求最短路径的和改为求最大载重量的问题，关键是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}