I think this problem solve by Dijkstra Algorithm. 
and I don't think this algorithm get TL or WA , in N<=1000,T<=2000
but.,,.,.,
I got WA... It's very strange .. :(
please help me .

My Code : 
/***CodeStart***/
#include <stdio.h>

int t, n ; 
int a[ 1010 ][ 1010 ] ; 
int v[ 1010 ] ; 
int d[ 1010 ] ; 

void input();
void process();
void output();
 
int main()
{
	input();
	process();
	output();
	return 0 ; 
}
void input()
{
	scanf("%d %d",&t,&n);
	int i ,  j ;
	for ( i = 1 ; i <= n ; i ++ )
		for ( j = 1 ; j <= n; j ++ )
		{
			if ( i == j ) a[i][j] = 0 ;
			else a[i][j] = 2100000000 ; 
		}
	int t1, t2 , t3 ; 
	for ( i = 0 ; i < t ; i ++ )
	{
		scanf("%d %d %d",&t1,&t2,&t3 ) ;  
		a[t1][t2] = t3 ; 
		a[t2][t1] = t3 ; 
	}
}
void process()
{
	int i , j ;
	int min , mini ; 
	for ( i = 1 ; i <= n ; i ++ ) 
	{
		d[i] = 2100000000 ; 
		v[i] = 0 ;
	}
	d[1]=0;
	for ( i = 1 ; i <= n ; i ++ ) 
	{
		min = 2100000000; 
		for ( j = 1 ; j <= n ; j ++ )
		{
			if ( v[j] == 0 && min > d[j] )
			{
				min = d[j] ;
				mini = j ;
			}
		}
		v[mini] = 1 ; 
		for ( j = 1 ; j <= n ; j ++ )
			if ( d[j] > d[mini] + a[mini][j] ) 
				d[j] = d[mini] + a[mini][j] ; 
	}
}

void output()
{
	printf("%d\n",d[n]);
}
/*** Code End ***/

• there can be double edges (1482) kcm1700 2006-06-03 18:56:21