说白了就是给你一张图，每一个点有一个等级限制，在等级限制以内求一条最短路。

构图方法：首先将原点0连向每个物品相应的编号，那么边权为物品的初始价格；假设对于物品j，假设有了物品i，那么j的优惠价为w，就在i,j之间连一条权值为w的边。最后枚举等级的范围(注意等级的上下差为m，当中包括了酋长的等级，而不是与酋长等级差的绝对值小于等于m QAQ)，求到原点到酋长(0号点到1号点)的最短路。

#include

#include

#include

#include

using namespace std;

struct T

{

int v;

int w;

int next;

}edge[10010];

int head[110],cnt;

void add_edge(int u,int v,int w)

{

edge[cnt].v = v;

edge[cnt].w = w;

edge[cnt].next = head[u];

head[u] = cnt++;

}

int m,n;

int abs(int x)

{

return x>0?x:-x;

}

int dis[110];

int lv[110];

bool vis[110];

void BFS(int dn,int up)//求最短路

{

memset(dis,0x3f,sizeof dis);

memset(vis,0,sizeof vis);

queue myque;

dis[0] = 0;

vis[0] = 1;

myque.push(0);

while(!myque.empty())

{

int u = myque.front();

myque.pop();

for(int i = head[u]; i != -1; i = edge[i].next)

{

int v = edge[i].v;

int w = edge[i].w;

if(!vis[v]&&lv[v] >= dn&&lv[v] <= up)

{

if(dis[u] + w < dis[v])

dis[v] = dis[u] + w;

myque.push(v);

vis[v] = 1;

}

else if(dis[u] + w < dis[v]&&lv[v] >= dn&&lv[v] <= up)

dis[v] = dis[u] + w;

}

}

}

int main()

{

memset(head,-1,sizeof head);

int p,x;

int y,z;

scanf("%d%d",&m,&n);

for(int i = 1; i<= n; i++)

{

scanf("%d%d%d",&p,&lv[i],&x);

add_edge(0,i,p);

add_edge(i,0,p);

for(int j = 1; j <= x; j++)

{

scanf("%d%d",&y,&z);

add_edge(y,i,z);

add_edge(i,y,z);

}

}

int ans = 123456789;

for(int i = lv[1]-m; i <= lv[1]; i++)//枚举等级范围

{

BFS(i,i+m);

if(dis[1] < ans)

ans = dis[1];

}

printf("%d\n",ans);

}

推荐链接

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。