本文共 1589 字，大约阅读时间需要 5 分钟。
一道读题读的不明所以的题...
每个人只能接受和自己等级差距不超过m的人进行交易 包括间接交易
所以我们可以枚举每一个长度为m的围绕着酋长的等级区间 每次都对这个等级区间内的人进行操作 求dis[1]
在这里的建图方式是很难得的灵光一现呢..
将0点作为源点 每一个物品的本身直接购买的价值设为初始值 对它们进行所给等级区间允许内的松弛操作 找出其中最小的dis[1]
#include #include #include #include #include #include #include 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\n",ans); }}
转载于:https://www.cnblogs.com/rayrayrainrain/p/5551076.html