#include <stdio.h>
#include <malloc.h>
int dist[30003], m, n;
int heap[30003], bold;

struct arc{
	int end;
	int w;
	struct arc * nextarc;
} adjList[30003];

inline void swap( int *x, int *y )
{
	int k;
	k=*x;
	*x=*y;
	*y=k;
}

void Modify( )
{
	int i, t, k=bold>>1;
	
	if( bold%2 )
		if( dist[ heap[k] ] > dist[ heap[bold] ] )
			swap( &heap[k], &heap[bold] );
	if( dist[ heap[k] ] > dist[ heap[k<<1] ] )
		swap( &heap[k], &heap[k<<1] );
	
	for( i=k-1; i>=1; i-- )
	{
		t=i<<1;
		if( dist[ heap[t] ] < dist[ heap[i] ] )
			swap( &heap[t], &heap[i] );
		if( dist[ heap[t+1] ] < dist[ heap[ i ] ] )
			swap( &heap[t+1], &heap[i] );
	}
}


int PopNode( )
{
	int x;
	Modify( );
	x=heap[1];
	heap[1]=heap[bold];
	bold--;
	return x;
}

int solve( )
{
	int u, i, nt;
	struct arc * pt;
	bold=n;
	for( i=1; i<=n; i++ )
	{
		heap[ i ]=i;
		dist[ i ]=0x7fffffff;
		adjList[i].w = 1;
	}
	dist[1] = 0;
	for( i=1; i<=n; i++ )
	{
		u = PopNode( );
		adjList[u].w = 0;
		pt=adjList[ u ].nextarc;
		while( pt )
		{
			nt= pt->end;
			if( adjList[ nt ].w !=0 && dist[u]+ ( pt->w) <  dist[ nt ] )
				dist[ nt ] = dist[ u ] + ( pt->w );
			pt = pt->nextarc;
		}
	}
	
	return dist[n];
}

int main( )
{
	int i, a, b, c;
	struct arc *pp;
	struct arc *pt;
	
	scanf("%d%d", &n, &m);
	
	for( i=0; i<m; i++ )
	{
		scanf( "%d%d%d", &a, &b, &c );
		pt=(struct arc *)malloc( sizeof(struct arc) );
		pp=&(adjList[a]);
		while( pp->nextarc )
			pp=pp->nextarc;
		pp->nextarc=pt;
		pt->end = b;
		pt->w = c;
		pt->nextarc = NULL;
	}
	
	printf( "%d\n", solve( ) );
	
	return 0;
}

• 有什么特殊数据吗,一直在3332K时WA,实在找不到算法上的错误了.... (0) TopBoy 2007-01-15 13:10:02
  • 刚发了贴就找到错误数据了.^_^ (0) TopBoy 2007-01-15 13:14:30
    • 过了,谢谢大家,呵呵 (0) TopBoy 2007-01-15 13:31:59