由于物品编号从1开始，我们假定0也是一个物品作为起点，它到其它物品的距离就是各个物品的原始价值。开始时，如果两种物品主人的等级限制M在规定范围以内，且j能用i替换，则将优惠价格视作从i到j的一条权值为优惠价的路径；如果在范围以外，就设为INF。
由于题目中说：“但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。”所以单纯用一次单源最短路径是不可以的 。我们依次枚举每一个物品，将它的等级L作为交易中等级最高的那一个，即可以参与交易的等级范围为[L-M,L]，预处理时将这个范围以外的物品强制设置为已经访问过，再进行Dijkstra即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN=+;
const int INF=0x7fffffff;
struct Rec
{
int p,l,x;
/*依次表示该物品的价格、主人的地位等级和替代品总数*/
int ins[MAXN];//替代品的编号
int sal[MAXN];//替代品的优惠价
};
Rec ob[MAXN];
int m,n;
int map[MAXN][MAXN];
int vis[MAXN];
int ans; int dijkstra()
{
int trade[MAXN];
for (int i=;i<=n;i++) trade[i]=ob[i].p;
for (int i=;i<=n;i++)
{
int minnum=INF,minn;
for (int j=;j<=n;j++)
{
if (vis[j]== && trade[j]<minnum)
{
minnum=trade[j];
minn=j;
}
}
vis[minn]=;
if (minn==) break;
for (int j=;j<=n;j++)
if (!vis[j] && trade[j]>trade[minn]+map[minn][j]) trade[j]=trade[minn]+map[minn][j];
}
return trade[];
} int main()
{
scanf("%d%d",&m,&n);
memset(map,0x7F,sizeof(map));
for (int i=;i<=n;i++)
{
scanf("%d%d%d",&ob[i].p,&ob[i].l,&ob[i].x);
map[][i]=ob[i].p;
for (int j=;j<ob[i].x;j++)
scanf("%d%d",&ob[i].ins[j],&ob[i].sal[j]);
}
for (int i=;i<=n;i++)
for (int j=;j<ob[i].x;j++)
{
if (abs(ob[i].l-ob[ob[i].ins[j]].l)<=m)
map[ob[i].ins[j]][i]=ob[i].sal[j];
} ans=INF;
for (int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
vis[]=;
int maxl=ob[i].l;
for (int j=;j<=n;j++)
if (i!=j)
if (ob[j].l>maxl || ob[j].l<maxl-m) vis[j]=; int nowans=dijkstra();
if (nowans<ans) ans=nowans;
} cout<<ans<<endl;
return ;
}