问题描述
有个蘑菇精想要成仙，但是他必须要收集10000个精灵宝石，不过他要是有花精灵的泪水，就只要8000个精灵宝石就可以了，或者如果他有花精灵的血滴，就只要5000个精灵宝石便可以成仙了。蘑菇精可以和森林里的其他精灵交换东西，但是修为等级差距过大的交换会影响
修炼
蘑菇精就跑到花精灵那里，向他索要泪水或血滴，花精灵要他用精灵宝石来换，或者替他弄来
其他的东西，他可以降低价格。蘑菇精于是又跑到其他地方，其他精灵也提出了类似的要求，
或者直接用精灵宝石换，或者找到其他东西就可以降低价格。不过蘑菇精没必要用多样东西去
换一样东西，因为这不会得到更低的价格。
蘑菇精现在很需要你的帮忙，让他用最少的精灵宝石帮助他成仙。另外他要告诉你的是，在这
个森林里，交换东西，修为差距超过一定限制的两个精灵之间不会进行任何形式的直接接触，
包括交易，否则会影响修炼。
蘑菇精是外来精灵，所以可以不受这些限制。但是如果他和某个修为等级较低的精灵进行了交
易，修为等级较高的的精灵有可能不会再和他交易，他们认为这样等于是间接接触，反过来也
一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从 开始进行编号，成仙也看作一个物品，并且编号总是1。每个物品都有对应的代价 P，主人精灵的修为等级L ，以及一系列的替代品Ti和该替代品所对应的“优惠”Vi 。如果两个精灵修为等级差距超过了M ，就不能“间接交易”。你必须根据这些数据来计算出蘑菇精最少需要多少精灵宝石才能成仙。
输入格式
第一行是两个整数 ，依次表示修为等级差距限制和M,N(1< =M< =20,1< =N< =20000)物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是P,L,X三个非负整数 （ X< N），依次表示该物品的代价、主人精灵的修为等级和替代品总数。接下来X 行每行包括两个整数T 和V ，分别表示替代品的编号和“优惠价格”。(Σx< =200000)
输出格式
对于每个测试数据，在单独一行内输出最少需要的精灵宝石数。
样例输入
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
样例输出
5250
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
int L[200010];
using namespace std;
int MAXN=70000;
int p[70000];
bool inq[70000];
long long d[200010];
int INF=0x3f3f3f3f;
int eid;
int n,m;
struct edge
{
int v;
int next;
int w;
}e[500000];
int edgeinsert(int wei,int u,int v)
{
e[eid].v=v;
e[eid].w=wei;
e[eid].next=p[u];
p[u]=eid++;
}
int init()
{
memset(p,-1,sizeof(p));
eid=0;
}
void SPFA(int st,int xiuwei)
{
memset(inq,false,sizeof(inq));
memset(d,INF,sizeof(d));
d[st]=0;
inq[st]=true;
queue<int>q;
q.push(st);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
for(int i=p[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if((L[v]>=xiuwei)&&(L[v]<=xiuwei+m)&&(d[u]+e[i].w<d[v]))
{
d[v]=d[u]+e[i].w;
if(!inq[v])
{
q.push(v);
inq[v]=true;
}
}
}
}
return;
}
int main()
{
init();
cin>>m>>n;
for(int i=1;i<=n;i++)
{
int p,x;
cin>>p>>L[i]>>x;
edgeinsert(p,0,i);
while(x--)
{ int a,b;
cin>>a>>b;
edgeinsert(b,a,i);
}
}
long long ans=INF;
for(int i=L[1];i+m>=L[1];i--)
{
SPFA(0,i);
ans=min(d[1],ans);
}
cout<<ans;
return 0;
}