AcWing 903. 昂贵的聘礼

聘礼"/>

AcWing 903. 昂贵的聘礼

昂贵的聘礼

大意：给定一个物品，以及购买它的价值，可以直接购买，或者可以通过其他提前获得其他物品，然后花较少的金币进行换购，给定换购的关系，并且每个物品有一个等级，购买的一系列物品等级差值的最大值不能超过 M。求最终能购买到这个物品所花费的最小价值。

思路：对于问题一步一步分析，我们先不考虑等级的限制，对于任意一个物品y,假设它可以通过物品 x 再加上一些金币w换购，那么我们可以从 x 向 y连一条有向边，权重为 w，并且对于x,y 也可以不需要换购，直接够买，所以我们可以建立一个虚拟源点，连有向边，权重就是直接购买的价值，然后就将问题转化成了将 虚拟源点看成起点，要购买的物品看成终点，求最短路径。接下来再看等级的限制，因为数据不大，我们可以直接枚举等级区间，每次求最短路径的是，所能用的点都是等级区间的点。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=110,M=998244353;
typedef long long LL;
int m,n;
int g[N][N];
int le[N],d[N];
bool st[N];
int dijkstra(int l,int r)
{memset(st,0,sizeof st);memset(d,0x3f,sizeof d);d[0]=0;for(int i=0;i<=n;i++){int t=-1;for(int j=0;j<=n;j++)if(!st[j]&&(t==-1||d[j]<d[t]))t=j;st[t]=1;for(int j=0;j<=n;j++)if(le[j]>=l&&le[j]<=r)d[j]=min(d[j],d[t]+g[t][j]);}return d[1];
}
void solve()
{cin>>m>>n;memset(g,0x3f,sizeof g);for(int i=1;i<=n;i++){int p,x;cin>>p>>le[i]>>x;g[0][i]=min(g[0][i],p);while(x--){int t,v;cin>>t>>v;g[t][i]=min(g[t][i],v);}}int ans=0x3f3f3f3f;for(int i=le[1]-m;i<=le[1];i++)ans=min(ans,dijkstra(i,i+m));cout<<ans<<"\n";
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int _=1;//cin>>_;while(_--)solve();return 0;
}

总结：图论的问题重点在于建图，要多做题