poj 1797 Heavy Transportation

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;}