一道读题读的不明所以的题...
每个人只能接受和自己等级差距不超过m的人进行交易 包括间接交易
所以我们可以枚举每一个长度为m的围绕着酋长的等级区间 每次都对这个等级区间内的人进行操作 求dis[1]
在这里的建图方式是很难得的灵光一现呢..
将0点作为源点 每一个物品的本身直接购买的价值设为初始值 对它们进行所给等级区间允许内的松弛操作 找出其中最小的dis[1]
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<queue>
#include<iostream>
using namespace std;
int m,n;
int dis[105];
int a[105];
struct node
{
int v;
int nex;
int w;
};
node b[30050];
int point [105];
int level[105];
bool vis[105];
int cnt;
void init()
{
cnt=0;
for(int i=1; i<=n; i++)
point[i]=-1;
for(int i=1; i<=n; i++)
vis[i]=true;
}
void add(int u,int v,int w)
{
b[cnt].v=v;
b[cnt].w=w;
b[cnt].nex=point[u];
point[u]=cnt;
cnt++;
}
void dij(int l,int r)
{
for(int i=1; i<=n; i++)
{
int p=-1;
int minn=999999999;
for(int k=1; k<=n; k++)
{
if(vis[k]&&minn>dis[k])
{
minn=dis[k];
p=k;
}
}
if(p==-1)
return ;
vis[p]=false;
for(int tt=point[p]; tt!=-1; tt=b[tt].nex)
{
int v=b[tt].v;
int w=b[tt].w;
if(level[v]>=l&&level[v]<=r&&level[p]>=l&&level[p]<=r&&vis[v])
{
if(dis[v]>w+dis[p])
{
dis[v]=dis[p]+w;
}
}
}
}
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
init();
for(int i=1; i<=n; i++)
{
int p;
int l,x;
scanf("%d%d%d",&p,&l,&x);
level[i]=l;
a[i]=p;
for(int k=1; k<=x; k++)
{
int d;
int w;
scanf("%d%d",&d,&w);
add(d,i,w);
}
}
for(int i=1; i<=n; i++)
dis[i]=a[i];
int ans=999999999;
for(int l=level[1]-m; l<=level[1]; l++)
{
int r=l+m;
for(int i=1; i<=n; i++)
vis[i]=true;
for(int i=1; i<=n; i++)
dis[i]=a[i];
dij(l,r);
if(ans>dis[1])
ans=dis[1];
}
printf("%d
",ans);
}
}