HDu 2544最短

#include <stdio.h>
#define MAX 100005
#define INF 100000
// c,      ？？？ AC
int map[MAX][MAX];
int dist[MAX],visit[MAX];

void Dijkstra(int s,int n)
{
	int i,j,min,v;
	for(i=1;i<=n;i++)
	{
		dist[i]=map[s][i];
		visit[i]=0;
	}
	dist[1]=0;
	visit[1]=1;
	for(i=1;i<=n;i++)
	{
		min=MAX;
		v=1;
		for (j=1;j<=n;j++)
		{
			if(!visit[j]&&dist[j]<min)
			{
				min=dist[j];
				v=j;
			}
		}
		visit[v]=1;
		for(j=1;j<=n;j++)
			if(!visit[j]&&dist[j]>(dist[v]+map[v][j]))
				dist[j]=dist[v]+map[v][j];
	}
}

int main()
{
	int n,m,i,j,x,y,val;
	while(scanf("%d %d",&n,&m)&&n)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
				map[i][j]=INF;
		}
		while(m--)
		{
			scanf("%d %d %d",&x,&y,&val);
			if(val<map[x][y])
			{
				map[x][y]=val;
				map[y][x]=val;
			}
		}
		Dijkstra(1,n);
		printf("%d
",dist[n]);
	}
	return 0;
}