pku1062.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>
#define TheMax 100000000

int C[101][101];
int lev[101];
int levc[101];
int Dis, N;

int cp(const void *a, const void *b)
{
	return *(int *)b - *(int *)a;
}

int OK(int top, int now)
{
	if (top - now > Dis || top < now)
	{
		return 0;
	}
	return 1;
}

int pre()
{
	int i, j;
	for (i = 0; i <= N; i++)
	{
		C[i][i] = 0;
		for (j = i + 1; j <= N; j++)
		{
			C[j][i] = C[i][j] = TheMax;
		}
	}
}

int DIJ(int l)
{
	int mindis[101];
	int u[101];
	int i, j, k, min, minid;
	for (i = 1; i <= N; i++)
	{
		if (OK(l, lev[i]))
		{
			mindis[i] = C[0][i];
		}
		else
		{
			mindis[i] = TheMax;
		}
		u[i] = 0;
	}
	u[0] = 1;

	for (k = 0; k < N; k++)
	{
		min = TheMax;
		minid = -1;
		
		for (i = 0; i <= N; i++)
		{
			if (u[i] || OK(l, lev[i]) == 0)
			{
				continue;
			}
			if (mindis[i] < min)
			{
				minid = i;
				min = mindis[i];
			}
		}
		if (minid == -1)
		{
			break;
		}
		u[minid] = 1;
		for (i = 0; i <= N; i++)
		{
			if (!u[i] && OK(l, lev[i]) && mindis[i] > min + C[minid][i])
			{
				mindis[i] = min + C[minid][i];
			}
		}
	}
	return mindis[1];
}
int main()
{
	int i, j;
	int id, cid, cval, cnum, min, tmp;

	scanf("%d %d", &Dis, &N);
	
	pre();
	for (i = 1; i <= N; i++)
	{
		scanf("%d %d %d", &C[0][i], &lev[i], &cnum);
		while (cnum--)
		{
			scanf("%d %d", &cid, &cval);
			C[cid][i] = cval;
		}
	}

	for (i = 1; i <= N; i++)
	{
		levc[i - 1] = lev[i];
	}
	qsort(levc, N, sizeof(levc[0]), cp);

	min = C[0][1];
	
	for (i = 0; i < N; i++)
	{
		if (OK(levc[i], lev[1]))
		{
			if (i > 0 && levc[i] == levc[i - 1])
			{
				continue;
			}
			
			tmp = DIJ(levc[i]);
			if (tmp < min)
			{
				min = tmp;
			}
		}
	}
	
	printf("%d\n", min);
	return 0;
}