赞
踩
年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了,于是便向酋长去求亲。酋长要他用 10000 个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币,便请求酋长降低要求。酋长说:”嗯,如果你能够替我弄到大祭司的皮袄,我可以只要 8000 金币。如果你能够弄来他的水晶球,那么只要 5000 金币就行了。”探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,或者替他弄来其他的东西,他可以降低价格。探险家于是又跑到其他地方,其他人也提出了类似的要求,或者直接用金币换,或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西,因为不会得到更低的价格。探险家现在很需要你的帮忙,让他用最少的金币娶到自己的心上人。另外他要告诉你的是,在这个部落里,等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触,包括交易。他是一个外来人,所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,他们认为这样等于是间接接触,反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。为了方便起见,我们把所有的物品从 1 开始进行编号,酋长的允诺也看作一个物品,并且编号总是 1。每个物品都有对应的价格 P P P,主人的地位等级 L L L,以及一系列的替代品 T i Ti Ti 和该替代品所对应的”优惠” V i Vi Vi。如果两人地位等级差距超过了 M M M,就不能”间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
输入格式
输入第一行是两个整数
M
M
M,
N
N
N,依次表示地位等级差距限制和物品的总数。
接下来按照编号从小到大依次给出了 N N N 个物品的描述。
每个物品的描述开头是三个非负整数 P P P、 L L L、 X X X,依次表示该物品的价格、主人的地位等级和替代品总数。
接下来 X 行每行包括两个整数 T T T 和 V V V,分别表示替代品的编号和”优惠价格”。
输出格式
输出最少需要的金币数。
数据范围
1
≤
N
≤
100
1≤N≤100
1≤N≤100,
1
≤
P
≤
10000
1≤P≤10000
1≤P≤10000,
1
≤
L
,
M
≤
N
1≤L,M≤N
1≤L,M≤N,
0
≤
X
<
N
0≤X<N
0≤X<N
输入格式
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
输出格式
5250
咳咳,本蒟蒻深夜做题,最短路刚刚入门(感觉这题还是挺有意思的),因此写这题时还是有很多感触的(从acwing上搬题,排版不好看,见谅)
废话说了那么多,最后还是上代码~~~
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=110; int w[N][N],dist[N],level[N],n,m,res=0x3f3f3f3f; bool st[N]; int dij(int left,int right){ memset(dist,0x3f,sizeof(dist)); memset(st,0,sizeof st);//不要忘了memset,因为要m+1次 dist[0]=0; for(int i=1;i<=n;i++){ int t=-1; for(int j=0;j<=n;j++){//j要从0开始,0是虚拟源点 if(!st[j] && (t==-1 || dist[j]<dist[t])){ t=j; } } st[t]=1; for(int j=1;j<=n;j++){ if(level[j]>=left && level[j]<=right){ dist[j]=min(dist[j],dist[t]+w[t][j]); } } }//Dijkstra模板 return dist[1]; } int main(){ memset(w,0x3f,sizeof w); cin>>m>>n; for(int i=1;i<=n;i++) w[i][i]=0;//i到i的点 for(int i=1;i<=n;i++){ int price,cnt; cin>>price>>level[i]>>cnt; w[0][i]=min(w[0][i],price);//0到i之间连了一条价格为price的边 //(min是防止重边) (虚拟源点设成0) while(cnt--){ int id,cost; cin>>id>>cost; w[id][i]=min(w[id][i],cost);//id到i之间连了一条边权为cost的边 } } for(int i=level[1]-m;i<=level[1];i++){ res=min(res,dij(i,i+m));//每个i即等级跑一遍Dijkstra } cout<<res<<endl; return 0; }
#include <iostream> #include <cstring> #include <queue> #include <cstdio> #include <vector> using namespace std; const int N=10010;//这里要存边,数据范围要开到10000+,不然会Segmentation Fault //(~~别问我怎么知道的~~) int idx,e[N],n,m,ne[N],v[N],level[N],dist[N],h[N],res=0x3f3f3f3f; bool st[N]; typedef pair<int,int> PII; void add(int a,int b,int c){ e[idx]=b,v[idx]=c,ne[idx]=h[a],h[a]=idx++;//邻接表存图 } int dij(int left,int right){ memset(dist,0x3f,sizeof dist); memset(st,0,sizeof st); dist[0]=0; priority_queue<PII,vector<PII>,greater<PII>> heap; heap.push({0,0});//这里也一样,将0号点入队 while(heap.size()){ PII t=heap.top(); heap.pop(); int ver=t.second,distance=t.first; if(st[ver]) continue; st[ver]=1; for(int i=h[ver];i!=-1;i=ne[i]){ int j=e[i]; if(level[j]>=left && level[j]<=right){//同样要判断等级限制范围 if(dist[j]>distance+v[i]){ dist[j]=distance+v[i]; heap.push({dist[j],j}); } } } } return dist[1]; } int main(){ cin>>m>>n; memset(h,-1,sizeof h); for(int i=1;i<=n;i++){ int price,cnt; cin>>price>>level[i]>>cnt; add(0,i,price);//0到i建一条边权为price的边,min防止重边 while(cnt--){ int id,cost; cin>>id>>cost; add(id,i,cost); } } for(int i=level[1]-m;i<=level[1]+m;i++){ res=min(res,dij(i,i+m)); } cout<<res<<endl; return 0; }
#include <iostream> #include <cstring> #include <queue> #include <vector> using namespace std; const int N=10010; int idx,dist[N],e[N],ne[N],h[N],v[N],n,m,level[N],res=0x3f3f3f3f; bool st[N]; void add(int a,int b,int c){ e[idx]=b; v[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int spfa(int left,int right){ memset(dist,0x3f,sizeof dist); memset(st,0,sizeof st); dist[0]=0; queue<int> q; q.push(0); st[0]=1; while(q.size()){ int t=q.front(); q.pop(); st[t]=0; for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(level[j]>=left && level[j]<=right){ if(dist[j]>dist[t]+v[i]){ dist[j]=dist[t]+v[i]; if(!st[j]){ q.push(j); st[j]=1; } } } } } return dist[1]; } int main(){ cin>>m>>n; memset(h,-1,sizeof h); for(int i=1;i<=n;i++){ int price,cnt; cin>>price>>level[i]>>cnt; add(0,i,price); while(cnt--){ int id,cost; cin>>id>>cost; add(id,i,cost); } } for(int i=level[1]-m;i<=level[1];i++) res=min(res,spfa(i,i+m)); cout<<res<<endl; return 0;//思路与堆优化版的Dijkstra是一样的,就是把模板换了换 }
如果真有能看到这里的大佬,本蒟蒻真的十分感谢,因为也没怎么写过题解,如有错误,请大佬多多包涵(doge)(/拜谢//拜谢//拜谢/)!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。