poj 2387 Til the Cows Come Home

Til the Cows Come Home

套路链接：http://poj.org/PRoblem?id=2387

这个题目没什么弯路直接套用迪杰斯特拉模板即可；

#include<stdio.h>
int map[1005][1005];
int vi[1005],dis[1005];
#define INF 100000000

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 min=INF;
		for(int j=1;j<=n;j++)
		{
			if(!vi[j] && dis[j]<min)
			{
				min=dis[j];
				p=j;
			}
		}
		vi[p]=1;
		for(int j=1;j<=n;j++)
		{
			if(!vi[j] && dis[j]>map[p][j]+dis[p])
				dis[j]=map[p][j]+dis[p];
		}
	}
}

int main()
{
	int n,t;
	int x,y,d;
	while(~scanf("%d%d",&t,&n))
	{
		for(int i=0;i<1005;i++)
		{
			for(int j=0;j<1005;j++)
				map[i][j]=INF;
		}
		for(int i=0;i<t;i++)
		{
			scanf("%d%d%d",&x,&y,&d);
			if(d<map[x][y])
			{
				map[x][y]=map[y][x]=d;
			}
		}
		Dj(n);
		printf("%d\n",dis[n]);
		
	}
	return 0;
}