这道题主要问题就是在与M区间的问题，
dfs的话
最开始的区间为酋长的[degree-M, degree+M],以后每次访问节点都要更新上下限即：
新上限=min(新节点degree+M, 原上限)
新下限=max(新节点degree-M, 原下限)


如果用最短路径的话需要分别枚举区间:[d-M,d],[d-M+1,d+1],... ...,[d,d+M](d为酋长degree)范围内的点，找出最小值
这样看来感觉dfs来的更简单些
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits.h>
#include <cctype>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <vector>
#include <sstream>
#include <map>
#include <utility>

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::next_permutation;
using std::set;
using std::string;
using std::getline;
using std::queue;
using std::istringstream;
using std::vector;
using std::min;
using std::map;
using std::make_pair;
using std::swap;
using std::upper_bound;
using std::lower_bound;
using std::max;

struct NODE
{
	int prize;
	int degree;
	int quant;
	int replace[101];
	int vi[101];
} node[101];

bool vis[101];

int re;
int M, N;
int deg;

int dfs(int sub, int lu, int ld);
//int dfs(int sub);

int main()
{
	freopen("d:\\out.txt", "w", stdout);	
	freopen("d:\\in.txt", "r", stdin);
	memset(vis, 0, sizeof(vis));
	while(scanf("%d%d", &M, &N) == 2)
	{
		for(int i = 1; i <= N; ++i)
		{
			scanf("%d%d%d", &node[i].prize, &node[i].degree, &node[i].quant);
				for(int j = 0; j < node[i].quant; ++j)
					scanf("%d%d", &node[i].replace[j], &node[i].vi[j]);
		}
		//printf("%d\n", dfs(-1, 1));
		//deg = node[1].degree;
		printf("%d\n", dfs(1, node[1].degree+M, node[1].degree-M));
	}
	return 0;
}

//int dfs(int deg, int sub)  //int dfs(int sub)
int dfs(int sub, int lu, int ld)
{
	vis[sub] = true;
	if(node[sub].degree > deg)
		deg = node[sub].degree;
	int tre = node[sub].prize;
	int tpriz;
	for(int i = 0; i < node[sub].quant; ++i)
	{
		if(!vis[node[sub].replace[i]] && node[node[sub].replace[i]].degree <= lu && node[node[sub].replace[i]].degree >= ld)
		{
			//tpriz = dfs(deg, node[sub].replace[i]);
			tpriz =dfs(node[sub].replace[i], min(node[node[sub].replace[i]].degree+M, lu), max(node[node[sub].replace[i]].degree-M, ld));
			if(tpriz + node[sub].vi[i] < tre)
				tre = tpriz + node[sub].vi[i];
		}
	}
	vis[sub] = false;
	return tre;
}