#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 105;
int dis[maxn], vis[maxn], P[maxn], L[maxn];
struct EDGE{
	int v, w, next;
}E[maxn * maxn];
int head[maxn], tol, n, M;

void Init(){
	memset(head, -1, sizeof head);
	tol = 0;
}

void add_edge(int u, int v, int w){
	E[tol].v = v;
	E[tol].w = w;
	E[tol].next = head[u];
	head[u] = tol++;
}

int ans;
void dfs(int u, int min_l, int max_l, int res){
	if(res + P[u] < ans){
		ans = res + P[u];
	}
	for (int i = head[u]; i != -1; i = E[i].next){
		int v = E[i].v;
		if (vis[v]) continue;
		if(L[v] < min_l && max_l - L[v] > M) continue;
		else if(L[v] > max_l && L[v] - min_l > M) continue;
		vis[v] = 1;
		dfs(v, min(min_l, L[v]),max(max_l,L[v]), res + E[i].w);
		vis[v] = 0;
	}
}

int main(){
	//freopen("read.txt","r",stdin);
	int X, T, V;
	while (scanf("%d %d", &M, &n) != EOF){
		Init();
		for (int i = 1; i <= n; i++){
			scanf("%d %d %d", &P[i], &L[i], &X);
			while (X--){
				scanf("%d %d", &T, &V);
				add_edge(i, T, V);
			}
		}
		ans = INF;
		memset(dis, 0x3f, sizeof dis);
		memset(vis, 0, sizeof vis);
		dis[1] = 0;
		dfs(1, L[1], L[1], 0);
		for (int i = 1; i <= n; i++){
			if (dis[i] + P[i] < ans)
				ans = dis[i] + P[i];
		}
		printf("%d\n", ans);
	}
	return 0;
}

• Re:爆搜0ms水过，附上ac代码 (1559) Phtato 2016-02-06 17:19:24