题目描述
探险家想娶酋长的女儿，需要支付聘礼。
直接支付需要 10000 金币 (这是物品 1 的初始价格 P[1])。
可以通过获取其他物品来获得优惠。例如，获得物品 2 (大祭司的皮袄) 可以让聘礼降至 8000 金币。获得物品 3 (水晶球) 可以让聘礼降至 5000 金币。
这些替代品本身也需要获取，可以直接用金币购买 (价格 P[i])，或者通过获得它们的替代品来获得优惠 (价格 V)。
这是一个连锁反应：要获得物品 A 的优惠，可能需要先获得物品 B；要获得物品 B 的优惠，可能需要先获得物品 C，等等。
核心目标：找到获得物品 1 (酋长的允诺) 的最低总金币成本。
约束条件：
* 每个物品的主人有一个地位等级 L[i]。
* 探险家选择交易的对象时，所有交易对象（包括酋长，如果最终需要支付聘礼的话）的地位等级必须在一个范围 [Lmin,Lmax] 内，并且 Lmax−Lmin≤M。
* 探险家本人不受等级限制，但他一旦和某个等级的人交易，就设定了这个等级范围的约束。
样例
Input:
1 4 (M=1, N=4)
10000 3 2 (Item 1: P=10000, L=3, 2 substitutes)
2 8000 (Substitute 2 reduces cost of 1 to 8000)
3 5000 (Substitute 3 reduces cost of 1 to 5000)
1000 2 1 (Item 2: P=1000, L=2, 1 substitute)
4 200 (Substitute 4 reduces cost of 2 to 200)
3000 2 1 (Item 3: P=3000, L=2, 1 substitute)
4 200 (Substitute 4 reduces cost of 3 to 200)
50 2 0 (Item 4: P=50, L=2, 0 substitutes)
Output:
5250
样例解释:
- 酋长 (Item 1) 等级 L=3。
- 物品 2, 3, 4 的主人等级 L=2。
- 等级差距限制 M=1。
可能的方案：
- 直接付 10000: 只与酋长 (L=3) 交易。等级范围 [3, 3]。满足 3-3 <= 1。成本 10000。
- 用物品 2 换优惠:
- 需要获得物品 2。物品 2 主人 L=2。
- 交易对象：酋长 (L=3), 物品 2 主人 (L=2)。等级范围 [2, 3]。满足 3-2 <= 1。
- 获取物品 2 的方式：
- 直接买: 1000 金币。总成本 = 1000 (买 2) + 8000 (优惠后聘礼) = 9000。
- 用物品 4 换优惠:
- 需要获得物品 4。物品 4 主人 L=2。
- 交易对象：酋长 (L=3), 物品 2 主人 (L=2), 物品 4 主人 (L=2)。等级范围 [2, 3]。满足 3-2 <= 1。
- 获得物品 4：直接买 50 金币。
- 总成本 = 50 (买 4) + 200 (优惠后物品 2 价格) + 8000 (优惠后聘礼) = 8250。
- 用物品 3 换优惠:
- 需要获得物品 3。物品 3 主人 L=2。
- 交易对象：酋长 (L=3), 物品 3 主人 (L=2)。等级范围 [2, 3]。满足 3-2 <= 1。
- 获取物品 3 的方式：
- 直接买: 3000 金币。总成本 = 3000 (买 3) + 5000 (优惠后聘礼) = 8000。
- 用物品 4 换优惠:
- 需要获得物品 4。物品 4 主人 L=2。
- 交易对象：酋长 (L=3), 物品 3 主人 (L=2), 物品 4 主人 (L=2)。等级范围 [2, 3]。满足 3-2 <= 1。
- 获得物品 4：直接买 50 金币。
- 总成本 = 50 (买 4) + 200 (优惠后物品 3 价格) + 5000 (优惠后聘礼) = 5250。
比较所有方案，最低成本是 5250。
算法：枚举等级范围 + 最短路 (Dijkstra)
核心思路
-
问题转化: 我们可以把这个问题看作一个最短路问题。
- 节点: 代表各个物品 (1 到 N)。
- 边: 代表获取物品的方式和成本。
- 目标: 找到获取物品 1 的最小成本。
-
边的构建:
- 直接购买: 对于每个物品
i，可以直接花费P[i]金币购买。 - 替代品优惠: 如果获得物品
j可以让物品i的价格降为V，这意味着“获得物品j”之后，再花费V就可以“获得物品i”。
- 直接购买: 对于每个物品
-
引入虚拟源点 (Virtual Source):
- 直接购买
P[i]不太好直接用图表示成A -> B的形式。 - 我们可以引入一个 虚拟源点，编号为 0。这个源点代表探险家的初始状态（只有金币）。
- 从虚拟源点 0 到每个物品节点
i连接一条边，权重为P[i]。这条边0 -> i代表“直接花费P[i]金币获得物品i”。 - 对于替代品优惠，如果物品
j可以让物品i的价格变为V，我们连接一条从节点j到节点i的边，权重为V。这条边j -> i代表“在已经获得物品j的基础上，再花费V获得物品i”。 - 现在，问题变成了：在构建好的图上，从虚拟源点 0 到节点 1 的最短路径长度是多少？
- 直接购买
-
处理等级限制:
- 等级限制
L_max - L_min <= M意味着我们不能在包含所有物品的完整图上直接跑最短路。 - 探险家可以选择与哪个等级范围的人交易。只要所有涉及的交易对象（物品的主人）的等级都在
[L_min, L_max]范围内，且L_max - L_min <= M，这次交易链就是有效的。 - 关键：酋长 (物品 1 的主人，等级
L[1]) 必须在这个等级范围内。 - 策略: 我们可以枚举所有可能的、包含酋长等级
L[1]的、满足宽度不超过M的等级区间[L_min, L_max]。 - 对于每一个合法的等级区间
[L_min, L_max]：- 构建一个 子图。这个子图只包含虚拟源点 0 和那些主人等级
L[i]在[L_min, L_max]区间内的物品节点i。 - 图中的边也只保留连接这些子图节点的边：
0 -> i(权重P[i]) 如果L[i]在[L_min, L_max]内。j -> i(权重V) 如果L[j]和L[i]都在[L_min, L_max]内。
- 在这个子图上，从源点 0 运行 Dijkstra 算法，计算到节点 1 的最短路径
dist[1]。 - 用这个
dist[1]更新全局的最小成本。
- 构建一个 子图。这个子图只包含虚拟源点 0 和那些主人等级
- 等级限制
-
枚举等级区间的实现:
- 我们可以枚举区间的下界
L_min。可能的L_min可以从L[1] - M到L[1]。 - 或者更简单，直接枚举所有可能的
L_min(例如从 1 到 N，或者题目中实际出现的最低等级)。 - 对于每个
L_min，对应的L_max可以是L_min, L_min + 1, ..., min(L_min + M, MaxLevel)(其中MaxLevel是所有物品主人等级的最大值)。 - 代码中的实现方式是：枚举
mn(作为L_min) 从 1 到 100 (假设等级不超过 100)，然后枚举mx(作为L_max) 从mn到min(mn + M, 100)。 - 在每次迭代
(mn, mx)时，检查L[1]是否在[mn, mx]内。如果是，则构建子图并运行 Dijkstra。
- 我们可以枚举区间的下界
-
Dijkstra 算法:
- 使用优先队列优化。
dist[i]存储从源点 0 到节点i的当前最短距离。初始化dist[0] = 0，其他为无穷大。- 优先队列存储
pair<cost, node>，按cost升序排列。 - 每次取出队首
{cost, u}，如果cost > dist[u]则跳过（已找到更短路径）。 - 遍历
u的邻居v（通过边u -> v权重w）：- 如果
dist[u] + w < dist[v]，则更新dist[v] = dist[u] + w，并将{dist[v], v}加入优先队列。
- 如果
- 算法结束后，
dist[1]就是在该等级区间限制下的最小成本。
-
最终结果: 遍历完所有合法的等级区间后，记录下的全局最小
dist[1]就是最终答案。
为什么使用虚拟源点？
- 统一模型: 最短路算法（如 Dijkstra）通常处理的是从一个源点出发到其他所有点的最短路径。我们的问题是“获得某个物品的最小成本”。
- 表示直接购买: 直接购买物品
i的成本P[i]不依赖于获得其他任何物品。它像是一个“初始成本”。虚拟源点0正好可以代表这个“初始状态”，边0 -> i的权重P[i]代表了从初始状态直接获得i所需的成本。 - 简化计算: 有了虚拟源点，所有获得物品的方式（直接购买或通过替代品）都可以统一为图中的路径。计算从
0到1的最短路，就自然地考虑了所有可能的获取方式组合，并找到了成本最低的那一种。
通用解法思路 (对于类似问题)
- 识别问题: 当题目要求“最小/最大成本/代价/时间”等，并且存在状态之间的转移（例如，获得 A 可以帮助获得 B），考虑图论，特别是最短路（最小化）或最长路（最大化）。
- 定义节点: 确定图中的节点代表什么。通常是问题中的实体、状态或目标（如此处的物品）。
- 定义边: 确定节点之间的关系以及相关的“成本”或“价值”。
- 初始成本/直接获取：通常可以用虚拟源点连接到对应节点，边权为初始成本。
- 依赖关系/状态转移：如果状态
j可以花费w转移到状态i，则添加边j -> i权重w。
- 处理约束: 如果存在全局约束（如此处的等级限制），导致不能在完整图上直接求解：
- 枚举约束子集: 像本题一样，枚举满足约束条件的子图，在每个子图上求解，然后取最优。
- 状态扩展: 如果约束可以加入到节点状态中（例如，带限制的最短路，
dp[node][constraint_state]），可以考虑使用多维 DP 或扩展节点状态的图算法。本题约束作用于整个求解过程，枚举子图更合适。
- 选择算法:
- 无负权边：Dijkstra (优先队列优化)。
- 有负权边但无负环：Bellman-Ford 或 SPFA。
- 有负环（求最短路无意义，或求是否存在负环）：Bellman-Ford 或 SPFA。
- DAG（有向无环图）：可以用拓扑排序 + DP。
- 虚拟源/汇点: 常用技巧，用于处理：
- 多个起点/终点问题：连接虚拟源到所有起点，或连接所有终点到虚拟汇点。
- 初始成本/固定收益：连接虚拟源/汇点。
时间复杂度
- 枚举等级范围：外层循环
mn从 1 到MaxLevel(假设 100)，内层循环mx最多M+1次。总共约O(MaxLevel * M)种范围。 - 对于每个范围：
- 构建子图：遍历所有 N 个节点和所有替代关系 (设总替代关系数为
X_{total}，最多N*(N-1))，复杂度O(N + X_{total})。 - 运行 Dijkstra：在子图上，节点数最多
N+1，边数最多N + X_{total}。复杂度O((N + X_{total}) log N)(使用优先队列)。
- 构建子图：遍历所有 N 个节点和所有替代关系 (设总替代关系数为
- 总复杂度：
O(MaxLevel * M * (N + X_{total}) log N)。 - 鉴于 N, M <= 100，
MaxLevel<= 100，X_{total}<= N*N，这个复杂度是可以接受的。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 inf = 2e18; // 定义一个常量 inf，表示无穷大，用于初始化距离和答案
int main() {
ios::sync_with_stdio(false); // 关闭 cin 和 cout 与 stdio 的同步，加速输入输出
cin.tie(nullptr); // 解除 cin 与 cout 的绑定，进一步提高效率
int m, n; // m: 地位等级的最大允许差距, n: 物品总数
cin >> m >> n;
// p: 存储每个物品的全价, l: 存储每个物品拥有者的地位等级
vector<int> p(n + 1), l(n + 1);
// sub: 存储每个物品的替代品列表, 每个替代品是一个 pair {替代品编号, 优惠价格}
vector<vector<pair<int, int>>> sub(n + 1);
// 输入处理：读取每个物品的信息
for (int i = 1; i <= n; i++) {
int x; // x: 物品 i 的替代品数量
cin >> p[i] >> l[i] >> x; // 输入物品 i 的全价、地位等级和替代品数量
for (int j = 0; j < x; j++) {
int t, v; // t: 替代品编号, v: 使用该替代品购买物品 i 的优惠价格
cin >> t >> v;
sub[i].push_back({t, v}); // 将替代品信息存入 sub[i]
}
}
i64 ans = inf; // 初始化答案为无穷大，表示尚未找到最小花费
// Lambda 函数 dijk: 使用 Dijkstra 算法计算从虚拟起点 0 到物品 1 的最小花费
auto dijk = [&](const vector<vector<pair<int, int>>>& g) {
vector<i64> d(n + 1, inf); // d: 存储从起点 0 到每个物品的最小花费，初始为无穷大
// 定义一个小根堆优先队列，存储 {当前花费, 物品编号}，按花费从小到大排序
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
d[0] = 0; // 虚拟起点 0 的花费为 0
pq.push({0, 0}); // 将起点 {花费=0, 编号=0} 加入优先队列
while (!pq.empty()) { // 当优先队列不为空时循环
auto [cost, u] = pq.top(); // 取出当前花费最小的物品 u 及其花费 cost
pq.pop(); // 移除队列顶部元素
if (cost > d[u]) continue; // 如果该记录已过时（已被更优路径更新），跳过
for (auto [v, w] : g[u]) { // 遍历 u 的所有邻居 v，w 是边的权重
i64 cur = d[u] + w; // 计算通过 u 到达 v 的总花费
if (cur < d[v]) { // 如果找到更优路径
d[v] = cur; // 更新到 v 的最小花费
pq.push({cur, v}); // 将新路径加入优先队列
}
}
}
return d[1]; // 返回从起点 0 到物品 1 的最小花费
};
// Lambda 函数 check: 检查并计算在地位等级区间 [mn, mx] 内的最小花费
auto check = [&](int mn, int mx) {
if (l[1] < mn || l[1] > mx) return; // 如果物品 1 的地位等级不在 [mn, mx] 内，无效，直接返回
vector<bool> in(n + 1); // in: 标记哪些物品的地位等级在当前区间 [mn, mx] 内
for (int i = 1; i <= n; i++) {
in[i] = l[i] >= mn && l[i] <= mx; // 判断物品 i 是否在区间内
}
// g: 图的邻接表表示，存储 {目标物品编号, 花费} 的边
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 1; i <= n; i++) {
if (in[i]) { // 如果物品 i 在区间内
g[0].push_back({i, p[i]}); // 添加从虚拟起点 0 到物品 i 的边，权重为全价 p[i]
for (auto [j, v] : sub[i]) { // 遍历物品 i 的替代品
if (in[j]) { // 如果替代品 j 也在区间内
g[j].push_back({i, v}); // 添加从 j 到 i 的边，权重为优惠价格 v
}
}
}
}
ans = min(ans, dijk(g)); // 调用 dijk 计算最小花费，并更新全局答案 ans
};
// 枚举所有可能的地位等级区间 [mn, mn + m]
for (int mn = 1; mn <= 100; mn++) { // mn: 区间下界，从 1 到 100
for (int mx = mn; mx <= mn + m && mx <= 100; mx++) { // mx: 区间上界，保证 mx - mn <= m
check(mn, mx); // 检查当前区间并更新答案
}
}
cout << ans << "\n"; // 输出最终的最小花费
return 0; // 程序结束
}
