$$\color{Purple}{kuangbin题解目录}$$
描述
年轻的探险家来到了一个印第安部落里。
在那里他和酋长的女儿相爱了,于是便向酋长去求亲。
酋长要他用 $10000$ 个金币作为聘礼才答应把女儿嫁给他。
探险家拿不出这么多金币,便请求酋长降低要求。
酋长说:”嗯,如果你能够替我弄到大祭司的皮袄,我可以只要 $8000$ 金币。如果你能够弄来他的水晶球,那么只要 $5000$ 金币就行了。”
探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,或者替他弄来其他的东西,他可以降低价格。
探险家于是又跑到其他地方,其他人也提出了类似的要求,或者直接用金币换,或者找到其他东西就可以降低价格。
不过探险家没必要用多样东西去换一样东西,因为不会得到更低的价格。
探险家现在很需要你的帮忙,让他用最少的金币娶到自己的心上人。
另外他要告诉你的是,在这个部落里,等级观念十分森严。
地位差距超过一定限制的两个人之间不会进行任何形式的直接接触,包括交易。
他是一个外来人,所以可以不受这些限制。
但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,他们认为这样等于是间接接触,反过来也一样。
因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见,我们把所有的物品从 $1$ 开始进行编号,酋长的允诺也看作一个物品,并且编号总是 $1$。
每个物品都有对应的价格 $P$,主人的地位等级 $L$,以及一系列的替代品 $T_i$ 和该替代品所对应的”优惠” $V_i$。
如果两人地位等级差距超过了 $M$,就不能”间接交易”。
你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
输入格式
输入第一行是两个整数 $M,N$,依次表示地位等级差距限制和物品的总数。
接下来按照编号从小到大依次给出了 $N$ 个物品的描述。
每个物品的描述开头是三个非负整数 $P、L、X$,依次表示该物品的价格、主人的地位等级和替代品总数。
接下来 $X$ 行每行包括两个整数 $T$ 和 $V$,分别表示替代品的编号和”优惠价格”。
输出格式
输出最少需要的金币数。
数据范围
$1 \\le N \\le 100$,
$1 \\le P \\le 10000$,
$1 \\le L, M \\le N$,
$0 \\le 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
思路
- 该题为
最短路
的变形,注意该题不仅要考虑边权
还得算上点权
,故考虑采用虚拟源点
的方式建图(其中虚拟源点(假设其编号为$0$)到每个点的边权
为当前每个点的点权
)(样例图如下),最后求从虚拟源点出发到编号为$1$的点的单源最短路
即可;- 其次关于
等级限制
的问题,可根据编号为$1$的等级$level$以及等级差距限制$m$划分为若干等级区间($[level-m,level],[level-m+1,level+1],…,[level,level+m]$,对每个等级区间跑一遍单源最短路
,记得将超过该区间范围内的点
排除在外.
代码
- $Dijkstra$(朴素版)
// Problem: 昂贵的聘礼
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/905/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-28 13:00:50
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 110
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int m,n;
int val[MAXN][MAXN];
int level[MAXN],vis[MAXN],dist[MAXN];
int Dijkstra(int start,int l,int r)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[start]=0;
for(int i=1;i<=n;i++)
{
int pos=-1;
for(int j=0;j<=n;j++)
if(vis[j]==0&&(pos==-1||dist[j]<dist[pos]))
pos=j;
vis[pos]=1;
for(int j=0;j<=n;j++)
if(level[j]>=l&&level[j]<=r)
dist[j]=min(dist[j],dist[pos]+val[pos][j]);
}
return dist[1];
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> m >> n;
memset(val,0x3f,sizeof(val));
//建立虚拟源点
for(int i=0;i<=n;i++)
val[i][i]=0;
for(int i=1;i<=n;i++)
{
int price,cnt;
cin >> price >> level[i] >> cnt;
val[0][i]=price;
for(int j=1;j<=cnt;j++)
{
int id,cost;
cin >> id >> cost;
val[id][i]=cost;
}
}
int res=inf;
for(int i=level[1]-m;i<=level[1];i++)
res=min(res,Dijkstra(0,i,i+m));
cout << res << endl;
return 0;
}
- $Dijkstra$(堆优化版)
// Problem: 昂贵的聘礼
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/905/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-28 13:00:50
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 110
#define MAXM 10010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int m,n;
int level[MAXN],vis[MAXN],dist[MAXN];
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
int Dijkstra(int start,int l,int r)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
priority_queue<PII,vector<PII>,greater<PII> > q;
dist[start]=0;
//q.push({0,start});
q.push(make_pair(0,start));
while(q.size()>0)
{
PII temp=q.top();
q.pop();
int temp_dis=temp.first,temp_pos=temp.second;
if(vis[temp_pos]==1)
continue;
vis[temp_pos]=1;
for(int i=head[temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[j]>temp_dis+val[i]&&level[j]>=l&&level[j]<=r)
{
dist[j]=temp_dis+val[i];
//q.push({dist[j],j});
q.push(make_pair(dist[j],j));
}
}
}
return dist[1];
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> m >> n;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
{
int price,cnt;
cin >> price >> level[i] >> cnt;
add(0,i,price);
for(int j=1;j<=cnt;j++)
{
int id,cost;
cin >> id >> cost;
add(id,i,cost);
}
}
int res=inf;
for(int i=level[1]-m;i<=level[1];i++)
res=min(res,Dijkstra(0,i,i+m));
cout << res << endl;
return 0;
}
- $spfa$
// Problem: 昂贵的聘礼
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/905/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-28 13:00:50
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 110
#define MAXM 10010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int m,n;
int level[MAXN],vis[MAXN],dist[MAXN];
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
int spfa(int start,int l,int r)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(start);
dist[start]=0;
vis[start]=1;
while(q.size()>0)
{
int temp=q.front();
q.pop();
vis[temp]=0;
for(int i=head[temp];i!=-1;i=nex[i])
{
int j=ed[i];
if(level[j]<l||level[j]>r)
continue;
if(dist[j]>dist[temp]+val[i])
{
dist[j]=dist[temp]+val[i];
if(vis[j]==0)
{
vis[j]=1;
q.push(j);
}
}
}
}
return dist[1];
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> m >> n;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
{
int price,cnt;
cin >> price >> level[i] >> cnt;
add(0,i,price);
for(int j=1;j<=cnt;j++)
{
int id,cost;
cin >> id >> cost;
add(id,i,cost);
}
}
int res=inf;
for(int i=level[1]-m;i<=level[1];i++)
res=min(res,spfa(0,i,i+m));
cout << res << endl;
return 0;
}