#include<iostream>
using namespace std;
#define INF 0x7ffffff
#define MAX 101
int map[MAX][MAX], value[MAX], lev[MAX], dist[MAX];
int m, n;
bool limit[MAX], visted[MAX];
//dijkstra求最短路径, dist[i]表示始点(1)到i点的花费
int dijkstra()
{
	int i, j, k, mindist;
	for(i=1; i<=n; i++)
	{
		dist[i] = map[1][i];
		visted[i] = 0;
	}
	for(i=1; i<=n; i++)
	{
		mindist = INF;
		//选取最小的dist值
		for(j=1; j<=n; j++)
		{
			if(!visted[j] && limit[j] && dist[j] < mindist)
			{
				k = j;
				mindist = dist[j];
			}
		}
		visted[k] = 1;
		//更新所有未访问节点的dist值
		for(j=1; j<=n; j++)
		{
			if(!visted[j] && limit[j])
				if(map[k][j] < INF && dist[k] + map[k][j] < dist[j])
					dist[j] = dist[k] + map[k][j];
		}
	}
	mindist = INF;
	for(i=1; i<=n; i++)
	{
		dist[i] += value[i];
		if(dist[i] < mindist)
			mindist = dist[i];
	}
	return mindist;
}
int main()
{
//freopen("in.txt","r",stdin);
	int i, j, t, tmp, min;
	while(scanf("%d%d", &m, &n) != EOF)
	{
		//构图
		for(i=1; i<=n; i++)
			for(j=1; j<=n; j++)
				map[i][j] = i==j?0:INF; 
		for(i=1; i<=n; i++)
		{
			scanf("%d%d%d", &value[i], &lev[i], &t);
			for(j=1; j<=t; j++)
			{
				scanf("%d", &tmp);
				scanf("%d", &map[i][tmp]);
			}
		}
		min = value[1];
		for(i=0; i<=m; i++)
		{
			memset(limit, 0, sizeof(limit));
			for(j=1; j<=n; j++)
				if(lev[j] >= lev[1] - m + i && lev[j] <= lev[1] + i)//枚举等级允许范围的结点
					limit[j] = 1;
			tmp = dijkstra();
			if(min > tmp)
				min = tmp;
		}
		printf("%d\n", min);
	}
	return 0;
}

• Re:WA, 给组数据测试下啊. (32) 20070861116 2010-07-17 13:18:17