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