昂贵的聘礼

题目描述：

n个物品，每个物品都有一个价值，且每个物品x都有一个替代队列，这个替代队列中，每个替代品y都有一个优惠价格c，你可以使用一个替代品y + 该替代品的优惠价格c换的所需物品x

每个物品还有一个尊贵等级，经过直接或者间接交换的物品的尊贵等级的差值的绝对值必须小于等于m

问最少花多少钱可以买到物品1

思路：

难懂的题意 ， 难搞的尊贵等级

可以把1号物品看出是终点，对于每个物品x，其替代队列中的物品y，可以在加c元的基础上换出x，所以我们可以从y到x建一条长度为c的边

因为起点是谁都可以，所以我们可以考虑建立一个超级源点0，从0连出一条指向i的权值为0的边，以0作为源点跑单源最短路

为了解决尊贵等级的限制，我们可以枚举每个尊贵等级，注意，尊贵等级的范围必须要包含第一个物品的等级，不然是无法买到第一个物品的

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)typedef long long ll;
typedef pair <int,int> pii;#define MAX 300000 + 50
int n, m;
int v, c;
int p[MAX], lr[MAX], k;int tot;
int head[MAX];
struct ran{int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){tr[++tot].to = v;tr[tot].val = c;tr[tot].nex = head[u];head[u] = tot;
}
int ans = inf;
int dis[105];
bool vis[105];
void dijkstra(int l, int r){mem(dis, inf);mem(vis, 0);priority_queue<pii, vector<pii>, greater<pii> >q;q.push(m_p(0, 0));dis[0] = 0;while (!q.empty()) {auto [d, u] = q.top();q.pop();if(vis[u])continue;vis[u] = 1;for(int i = head[u]; i; i = tr[i].nex){int v = tr[i].to;if(lr[v] >= l && lr[v] <= r && dis[v] > dis[u] + tr[i].val){dis[v] = dis[u] + tr[i].val;q.push(m_p(dis[v], v));}}}ans = min(ans, dis[1]);
}void work(){cin >> m >> n;for(int u = 1; u <= n; ++u){cin >> p[u] >> lr[u] >> k;add(0, u, p[u]);while (k--) {cin >> v >> c;add(v, u, c);}}for(int i = lr[1] - m; i <= lr[1]; ++i){dijkstra(i, i + m);}cout << ans << endl;
}int main(){io;work();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！