Heavy Transportation
题目链接:http://poj.org/PRoblem?id=1797
这个题目属于迪杰斯特拉算法的变形题了,大意是在通往目的地的所有路径中找到一条载重最大的道路,但是一条路径的载重由载重量最小的那条边决定。
转换公式:MAX(dis[j],MIN(dis[p],map[p][j])))
代码如下:
#include<stdio.h>int map[1005][1005];int vi[1005],dis[1005];#define INF 10000000 int MIN(int a,int b){ if(a<b) return a; return b;}void Dj(int n){ int p; for(int i=1;i<=n;i++) { dis[i]=map[1][i]; vi[i]=0; } vi[1]=1; for(int i=1;i<=n;i++) { int max=-1; for(int j=1;j<=n;j++) { if(!vi[j] && dis[j]>max) { max=dis[j]; p=j; } } vi[p]=1; for(int j=1;j<=n;j++) { if(!vi[j] && dis[j]<MIN(dis[p],map[p][j])) dis[j]=MIN(dis[p],map[p][j]); } }}int main(){ int index=0; int t; int n,m; int x,y,d; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<1005;i++) { for(int j=0;j<1005;j++) map[i][j]=-1; } for(int i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&d); map[x][y]=map[y][x]=d; Dj(n); printf("Scenario #%d:/n%d/n",++index,dis[n]); printf("/n"); } return 0;}
新闻热点
疑难解答