首页 > 代码库 > POJ 1797 Heavy Transportation
POJ 1797 Heavy Transportation
这题大概就是说从1 到n 选择一条载重最大的路 并求出最大值
要得出最大的载重量 我们就要求出每条路线能够负重的最小值
可以通过 dijkstra算法来求出
假设现在在x 点 在这之前的最大载重量为 d[x] 现在要通过路线 w[x][y] 到达y
我们就要将 d[x]和w[x][y] 进行比较 分类讨论得到 d[y]
#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffff#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int w[1200][1200];int d[1200];int v[1200];int main(){ int t,n,m,cas=1; int i,j; int a,b,c; cin>>t; while(t--) { printf("Scenario #%d:\n",cas++); cin>>n>>m; mem(w,0); mem(v,0); while(m--) { scanf("%d%d%d",&a,&b,&c); w[a][b]=w[b][a]=c; } for(int i=1;i<=n;i++) d[i]=(i==1?INF:0); for(i=1;i<=n;i++) { int x,maxx=0; for(int y=1;y<=n;y++) if(!v[y]&&d[y]>=maxx) maxx=d[x=y]; v[x]=1; for(int y=1;y<=n;y++) { if(d[x]>=w[x][y]&&w[x][y]>d[y]) { d[y]=w[x][y]; } else if(d[x]<w[x][y]&&d[x]>d[y]) { d[y]=d[x]; } } } cout<<d[n]<<endl<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。