记录编号	45054	评测结果	AAAAAAAAAA
题目名称	交换	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-10-22 08:55:45	内存使用	3.24 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int n,lim,cost[110],lowcost[110][110],lv[110],waynum[110],to[110][110],f[110];

int maxint(int a,int b)
{
	if (a>b)
		return(a);
	return(b);
}

int minint(int a,int b)
{
	if (a>b)
		return(b);
	return(a);
}

void fillit(int pos,int liml,int limr,int costnow)
{
	if (costnow>cost[1])/*deal with loop*/
		return;
	f[pos]=cost[pos];/*assumption*/
	int i,nliml,nlimr;
	nliml=maxint(liml,lv[pos]-lim);
	nlimr=minint(limr,lv[pos]+lim);
	for (i=1;i<=waynum[pos];i++)
	{
		if (lv[to[pos][i]]>=nliml&&lv[to[pos][i]]<=nlimr)
		{
			fillit(to[pos][i],nliml,nlimr,costnow+lowcost[pos][i]);
			f[pos]=minint(f[pos],f[to[pos][i]]+lowcost[pos][i]);
		}
	}
}

int main(void)
{
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
	int i,j;
	cin>>lim>>n;
	for (i=1;i<=n;i++)
	{
		cin>>cost[i]>>lv[i]>>waynum[i];
		for (j=1;j<=waynum[i];j++)
		{
			cin>>to[i][j]>>lowcost[i][j];
			if (lowcost[i][j]>cost[i])/*shortcut assignment*/
			{
				waynum[i]--;
				j--;
			}
		}
	}
	fillit(1,-100000000,100000000,0);
	cout<<f[1]<<endl;
	return(0);
}