问题 A: BBQ与比克大魔王
时间限制:2 Sec 内存限制:128 MB提交:91 解决:18
[ 提交][ 状态][ 讨论版]
题目描述
七夕,对BBQ来说是一个伤感的日子,因为他的女朋友被比克大魔王给抢走了。他不甘心自己一个人过七夕,所以他决定独自去救出心爱的女友。BBQ在S城堡,比克大魔王在E城堡,E城堡和S城堡之间有多个城堡,每2个城堡之间有一条可以互通的道路,但是每条道路有一定的载重量W。BBQ不可能赤手空拳去救自己的女朋友,他尽量想选择一个重型的武器(武器重量越大,攻击力越强)去救自己的女朋友。BBQ当然想挑选一把攻击力最强的武器来战胜比克大魔王。选好武器后,他一个人就出发。
输入
输入文件包含多个测试数据,每个测试数据的第一行为三个整数:城市的个数n(2<=n<=200),组成道路网络的道路的条数r(1<=r<=18800),武器的个数m(1<=m<=200)。
接下来有r行,每一行描述了一条直接连接两个城堡的道路,格式为:所连接的两个城堡的编号,道路的最大载重量。其中,重量限制为0到10000之间的整数,道路是双向的。
接着下一行,有m个整数,分别表示m个武器的重量,其重量限制为0到10000之间的整数。(不会出现重复的边)
最后一行是两个城堡的编号:S城堡和E城堡。
输入文件的最后一行是三个0,为n,r和m的取值,表示输入结束。
输出
帮BBQ选择一把最合适的武器。输出该武器的重量。
如果不存在合适的武器输出-1。
样例输入
4 3 51 2 1002 3 803 4 1 30 50 80 901 45 5 31 2 1002 3 803 4 1201 5 2205 4 17010 160 1804 10 0 0
样例输出
80160
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define INF 1000000int edge[220][220];int wu[220];int n,r,m;int main(){int i,j,k;int u,v,w;int s,e;while(cin>>n>>r>>m){if(n==0 && r==0 && m==0) break;for(i=1;i<=n;i++){for(j=1;j<=n;j++){edge[i][j]=0;if(i==j) edge[i][j]=INF;}}for(i=1;i<=r;i++){cin>>u>>v>>w;edge[u][v]=w;edge[v][u]=w;}for(i=0;i<m;i++)cin>>wu[i];sort(wu,wu+m);cin>>s>>e;for(i=1;i<=n;i++){for(j=1;j<=n;j++){for(k=1;k<=n;k++){ edge[j][k]=maxn(edge[j][k],minn(edge[j][i],edge[i][k]));//floyd的应用}}}for(i=m-1;i>=0;i--){if(wu[i]<=edge[s][e]){cout<<wu[i]<<endl;break;}}}return 0;}