1062.txt

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

#include"iostream.h"
#include"stdio.h"
#include"math.h"
#include"algorithm"

const int size=110;
typedef int type;

int maxl, minl;
int level[size], s[size];


type e[size][size];

////////////////////////////////////////////////////////////////////////////////////////////////
//	dijstra	????????1??????????0??
//	strat	??????
//	e		??????????
//	ans		??????????????????????

bool dijstra(int start,int n,type e[size][size],type ans[size])
{
	const type max=99999999;

	int i,j,k;
	type dis[size],temp;
	bool reach[size];

	for(i=0;i<n;i++)
		reach[i]=false,dis[i]=max;

	dis[start]=0;

	for(i=0;i<n;i++)
	{
		k=-1;
		for(j=0;j<n;j++)
		{
			if(	!reach[j] && level[j] <= maxl && level[j] >= minl	//dijstra 
				&&(k<0||dis[k]>dis[j]))
				k=j;
		}

		if( k < 0 )break;

		reach[k] = true;
		
		//judge
		if( k == n-1 ) break;
		//

		for(j=0;j<n;j++)
		{
			temp = dis[k] + e[k][j] ;
			
			if(dis[j]>temp)
				dis[j]=temp;
		}
	}

	for(j=0;j<n;j++)
		ans[j]=dis[j];

	return k>=0;
}

int dis[size];

int main()
{
	int n, m, i, j, f, h, k;

	scanf( "%d %d", &m, &n );

	for( i=0; i<=n; i++ )
	for( j=0; j<=n; j++ )
		e[i][j] = 999999;

	for( i=0; i<n; i++ )
	{
		scanf( "%d %d %d", &e[i][n], &level[i], &h );
		s[i] = level[i];
		for( j=0; j<h; j++ )
		{
			scanf( "%d %d", &k, &f );
			e[i][k-1] = f;
		}
	}

	std::sort( s, s+n );

	int ans = 99999;
	for( i=0; i<n; i++ )
	{
		minl = s[i], maxl = s[i]+m;
		
		if( level[0] >= minl && level[0] <= maxl )
		{
			dijstra( 0, n+1, e, dis );
		
			if( ans > dis[n] )
				ans = dis[n];
		}
	}

	printf( "%d\n", ans );

	return 0;
}