题解【POJ1062】昂贵的聘礼
2024-10-07 00:11:23
比较复杂的最短路模型转换。
我们考虑一种建图方式:
- 建立一个超级源点 \(S\),它向每一个节点连一条权值为那一个节点物品价值的边,表示直接购买那一个物品;
- 对于每一个节点,由它每一个可用的替代品向它连一条权值为当前替代品“优惠价格”的边,表示使用那一个替代品来购买当前物品。
- 最终答案即为 \(S\) 到 \(1\) 号节点的最短距离。
考虑等级限制,我们可以枚举当前最低的等级,然后在进行松弛操作的时候判断一下当前节点是否在当前等级限制之内。每一次跑完最短路后将答案与当前的 \(dist_1\) 取 \(\text{min}\)。
注意从 \(0\) 开始枚举最低等级。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 103, M = 20003;
int n, m;
int grade[N]; //每个物品的等级
int tot, head[N], ver[M], nxt[M], edge[M];
int dist[N], vis[N];
int S;
inline void add(int u, int v, int w)
{
ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}
inline void Dij(int s/*起点*/, int t/*终点*/, int LowGrade/*当前的最低等级*/, int HighGrade/*当前的最高等级*/)
{
memset(dist, 0x3f, sizeof dist);
priority_queue <pair <int, int> > q;
dist[S] = 0;
memset(vis, 0, sizeof vis);
q.push(make_pair(0, S));
while (!q.empty())
{
int u = q.top().second; q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = nxt[i])
{
int v = ver[i], w = edge[i];
if (grade[v] < LowGrade || grade[v] > HighGrade) continue; //不满足当前的等级限制
if (dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
if (!vis[v])
vis[v] = 1,
q.push(make_pair(-dist[v], v));
}
}
}
}
int main()
{
cin >> m >> n;
S = n + 1; //超级源点
for (int i = 1; i <= n; i+=1)
{
int u = i, v, w, x;
cin >> w >> grade[i] >> x;
add(S, u, w); //向超级源点连一条权值为物品价格的边
for (int j = 1; j <= x; j+=1)
cin >> v >> w,
add(v, u, w); //由替代品向当前物品连边
}
int ans = 2000000007;
for (int nowLowGrade = 0; nowLowGrade <= n; nowLowGrade+=1) //枚举最低等级,注意要从 0 开始
{
Dij(S, 1, nowLowGrade, nowLowGrade + m); //跑一次 Dijkstra 最短路
ans = min(ans, dist[1]); //将答案取最小值
}
cout << ans << endl;
return 0;
}
最新文章
- js在手机端不能正确显示
- POJ 3281	Dining 最大流
- Mysql-学习笔记(==》触发器 十一)
- 一些需要注意的C知识点
- iBatis 的简单入门
- jdbc详解(三)
- php curl详解用法[真的详解]
- executssql 函数的每一句代码的意思
- RabbitMQ的介绍及使用进阶(Docker+.Net Core)
- 解读 kubernetes client-go 官方 examples - Part Ⅰ
- HttpClientFactory与Steeltoe结合来完成服务发现
- 一种提升连接Dynamics 365性能的方法
- 小奶狗给小喵咪上CSS课程
- Rosserial实现Windows-ROS交互操作
- .net core WebApi Monitor实现并发同步
- 洛谷4782 【模板】2-SAT 问题
- poj 2262 Goldbach&#39;s Conjecture
- 【校招面试 之 C/C++】第13题 C++ 指针和引用的区别
- 星空灯改装成USB供电
- 3-Python内置结构-列表
热门文章
- Spring学习笔记:自动创建Proxy
- cmake处理多源文件目录的方法(转)
- 并发编程之Master-Worker模式
- 吴恩达deepLearning.ai循环神经网络RNN学习笔记_看图就懂了!!!(理论篇)
- 14-SSM整合
- 数据算法 --hadoop/spark数据处理技巧 --(17.小文件问题 18.MapReuce的大容量缓存)
- 安装python3.7
- linux系统的启动流程梳理
- 第三篇 SpringBoot整合log4j2详解
- 【HDU - 1176 】免费馅饼 (逆dp)