3811726_ac_32ms_248k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define INF 2100000000

int m, n, ans;
int level[101];
int map[101][101];
int dis[101];
int used[101];

int dij(int maxl, int minl)
{
	int i, j, tmp;

	for (i = 0; i < n; i++)
	{
		used[i] = 0;
		dis[i] = INF;
	}
	dis[0] = 0;
	while (used[n - 1] == 0)
	{
		tmp = INF;
		for (i = 0; i < n; i++)
		{
			if (level[i] != -1 && (level[i] > maxl || level[i] < minl))
				continue;
			if (used[i] == 0 && dis[i] < tmp)
			{
				tmp = dis[i];
				j = i;
			}
		}
		if (tmp == INF)
		{
			break;
		}
		used[j] = 1;
		for (i = 0; i < n; i++)
		{
			if (level[i] != -1 && (level[i] > maxl || level[i] < minl))
				continue;
			if (map[j][i] == -1)
				continue;
			if (tmp + map[j][i] < dis[i])
			{
				dis[i] = tmp + map[j][i];
			}
		}
	}
	return dis[n - 1];
}

void solve()
{
	int i, tmp;

	n++;
	for (i = 0; i < n; i++)
	{
		if (level[i] >= level[0] && level[i] - m <= level[0])
		{
			tmp = dij(level[i], level[i] - m);
			if (tmp < ans)
				ans = tmp;
		}
	}
}

int main()
{
	int i, j, u, num;

	scanf("%d%d", &m, &n);
	memset(map, -1, sizeof(map));
	for (i = 0; i < n; i++)
	{
		scanf("%d%d%d", &map[i][n], &level[i], &num);
		for (j = 0; j < num; j++)
		{
			scanf("%d", &u);
			u--;
			scanf("%d", &map[i][u]);
		}
	}
	level[n] = -1;
	ans = map[0][n];
	solve();
	printf("%d\n", ans);
	return 0;
}