2387.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 1000000000
#define NMAX 1002
long map[NMAX][NMAX];
long d[NMAX];
int final[NMAX]={0};
int T,N;
void solve()
{

	int start=1;
	int i,j;	
	for(i=1;i<=N;i++)
	{
		final[i]=0;
		if(map[start][i]<INF)
		{
			d[i]=map[start][i];
		}
	}
	
	final[start]=1;
	int k=INF;
	long min;
	for(i=1;i<=N;i++)
	{
        min=INF;
        for(j=1;j<=N;j++)
        {
            if(!final[j])
            {
				if(d[j]<min)
				{
					k=j;
					min=d[j];
				}
			}
		}
		if(k==INF)
			break;
		final[k]=1;

		
		for(j=1;j<=N;j++)
		{
			if((!final[j])&&(min+map[k][j]<d[j]))
			{
                d[j]=min+map[k][j];
				map[start][j]=d[j];
            }
		}
	}			
}

int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i,j;
	scanf("%d%d",&T,&N);
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
		{
			map[i][j]=INF;
		}
		d[i]=INF;
	}
	int a,b,c;
	for(i=1;i<=T;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		if(map[a][b]>c)
		{
			map[a][b]=c;
			map[b][a]=c;
		}
	}
	solve();
	printf("%d",d[N]);
#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}