对配方超边做 Dijkstra 式松弛，再按最小成本递增顺序统计最优方案数。
OJ: luogu
题目 ID: P1875
难度:提高
标签:最短路Dijkstra计数python
创建: 2026-07-17 03:00
更新: 2026-10-20 12:35
题意
药水可直接购买，也可由两份药水合成；求 0 号药水最小成本和最优方案数。
思路
初始距离是购买价格。某原料成本确定或下降时，检查包含它的配方 A+B->C，用 cost[A]+cost[B] 松弛 C。最小成本确定后，最优配方的原料成本都严格小于成品，按成本排序即可从低到高统计购买方案和合成方案。
配方是一条「超边」
普通图里，一个点的距离取所有入边的最小值，也就是多条前提之间的「或」（买？还是配？任选其一）。但一条配方内部是「与」：A 和 B 都要有，缺一不可。这种「一条尾巴挂两个节点」的边叫超边（hyperedge）：
拿它对照普通边：
| 普通边 | 配方超边 | |
|---|---|---|
| 尾部节点数 | 1 | 2（A 与 B） |
| 语义 | 一个前驱够了 | 两个前驱都到齐才放松 |
| 长度 | 边权 w |
cost[A] + cost[B] |
整张图于是是「普通边 + 超边」混合：商店 → i 是普通边（权 price[i]），{A,B} → C 是超边。每个点取所有入边（含超边）的最小值，这就是「或」套「与」。
拆点不能替代超边
一个自然的想法是把药水拆成 i1 → i2，用 a1→a2→b1→b2→c1→c2 串起来表达「与」。这条路走不通，因为路径只能串行，配方的两个原料是并行推导的。
具体看一个例子：a=1, b=100, p=1, q=1，配方 a+b→c 与 p+q→b。真值 cost_b = 2、cost_c = 3。
- 串成一条路径时，如果
b1→b2权取0（表示合成得到），则b免费，算出cost_c = 1，错； - 如果取
price_b = 100（表示购买），则b的便宜合成路线接不上去，算出101，也错。
根源在于：一条路径里同一份成本只能付一次，而「与」要求两条分支各付一次。 路径天然是「或」（多条路径取最短），表达不了需要同时满足的约束。
计数也能看出问题：超边上两个原料的选法要相乘 ways[A]*ways[B]；而路径计数会把「先 A 后 B」和「先 B 后 A」算成两条，但题面规定「1 份 A 混合 1 份 B」没有先后，于是会成倍高估。
超图上的 Dijkstra 为什么仍然成立
普通 Dijkstra 的定型论证靠「剩余边权非负，将来更远」。换成超边后，靠的是另一条不等式：
因为所有价格都是正数，所以一条超边的长度严格大于它任一尾部的成本，两个尾部都注满的时刻必然晚于任一单个尾部的时刻。于是「弹出当前最小候选 cur，它就已经是终值」的论证原封不动：将来任何通向它的超边，都要两个尾部先到齐，开出时刻不可能早于 cur。
代码里的 fixed_cost 正是这条超图的触发闸门：
if (!fixed_cost[other]) continue;对应「尾部没全部到齐就不允许放松」；if (fixed_cost[u] || cur != cost[u]) continue;对应普通 Dijkstra 的「已定型不再处理」。
把这条闸门去掉代码仍然正确（松弛只会让成本变小，没到齐时算出的候选必然偏高，等原料真正变便宜后会重新触发），但会多做约一倍的无效配方求值。它保护的是效率，不是正确性。
Python 知识
- EOF 输入用
read().split()，每三个整数切成一个配方元组。 by_ingredient记录「把 u 当原料的配方」，同一种原料只登记一次，避免自配方重复处理。heapify一次把所有购买方案放入堆；current != distance[potion]跳过堆里的过期记录。- 生成器求和表达
ways[A]*ways[B]的配方组合数。
代码
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-08-09 06:46
# update_at: 2026-10-20 10:51
#
# main.py：佳佳的魔法药水，求 0 号药水的最小花费与最优方案数。
# 两种得到药水的方式：直接买一份（price[i]），或用配方 A+B->C 合成（cost[A]+cost[B]）。
# 价格都是正数，合成花费严格大于两个原料各自的花费，所以配方是「两个原料都定型才能松弛」
# 的超边，仍可用 Dijkstra 的单调序处理：弹出当前最便宜的药水并定型，再看含它的配方，
# 若另一个原料也已定型就用两者花费之和松弛产物。
# 花费定型后按花费升序统计方案数：买一份算 1 种，每条 cost[A]+cost[B]==cost[C] 的配方
# 贡献 ways[A]*ways[B] 种（两个原料的选法互相独立）。
import sys
from heapq import heapify, heappop, heappush
# 输入以空行结束，所以统一按整数流读到底，再按位置切开
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0] # 药水总数，编号 0..n-1
price = data[1:n + 1] # 商店里 1 份 i 号药水的价格
recipes = [tuple(data[index:index + 3]) for index in range(n + 1, len(data), 3)]
# by_ingredient[u]：把 u 当原料的配方下标；同一种原料只登记一次，避免自配方重复
by_ingredient = [[] for _ in range(n)]
for index, (first, second, result) in enumerate(recipes):
by_ingredient[first].append(index)
if second != first:
by_ingredient[second].append(index)
# 第一阶段：Dijkstra 求最小花费。初始候选就是「直接买」。
distance = price[:]
heap = [(value, potion) for potion, value in enumerate(distance)]
heapify(heap)
while heap:
current, potion = heappop(heap)
if current != distance[potion]:
continue # 堆里的过期记录，这个药水已有更便宜的花费
for recipe_index in by_ingredient[potion]:
first, second, result = recipes[recipe_index]
# 两个原料此时都已定型（potion 自己刚定型，另一个也定型过才会走到这里），可以松弛
candidate = distance[first] + distance[second]
if candidate < distance[result]:
distance[result] = candidate
heappush(heap, (candidate, result))
# 第二阶段：按最小花费升序累计方案数
ways = [0] * n
recipes_by_result = [[] for _ in range(n)]
for first, second, result in recipes:
recipes_by_result[result].append((first, second))
# 最优配方的原料花费都严格小于产物，所以按花费升序保证原料先算完；
# 花费相同的药水之间不可能互为原料，同花费的先后顺序不影响结果
for potion in sorted(range(n), key=distance.__getitem__):
ways[potion] = price[potion] == distance[potion] # 直接买一份算 1 种方案
# 每条满足 cost[A]+cost[B]==cost[C] 的配方，贡献 ways[A]*ways[B] 种组合
ways[potion] += sum(ways[first] * ways[second] for first, second in recipes_by_result[potion]
if distance[first] + distance[second] == distance[potion])
print(distance[0], ways[0])原有 C++ 版本仍保留：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-17 01:40
* update_at: 2026-10-20 10:51
*/
// 佳佳的魔法药水：求 0 号药水的最小花费，以及花费最少的方案数。
// 两种得到药水的方式：直接买一份（花费 price[i]），或用配方 A+B->C 合成（花费 cost[A]+cost[B]）。
// 因为价格都是正数，合成花费严格大于两个原料各自的花费，所以配方是「两个原料都定型才能松弛」
// 的超边，仍可用 Dijkstra 的单调序处理：
// 每次弹出当前花费最小的药水并定型，再看含它的配方；
// 若配方的另一个原料也已定型（同一种原料只要求它自己定型），就用两者花费之和去松弛产物。
// 花费定型后再统计方案数：最优配方的原料一定比产物便宜，所以按花费升序扫一遍即可，
// 买一份算 1 种方案，每条满足 cost[A]+cost[B]==cost[C] 的配方贡献 ways[A]*ways[B] 种。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005; // 药水数上界 N <= 1000
const int MAXR = 500505; // 配方数上界：无序对 (A,B) 的结果唯一，约 n(n+1)/2
int n;
long long price[MAXN]; // 商店里 1 份 i 号药水的价格
long long cost[MAXN]; // 配出 1 份 i 号药水的最小花费
bool fixed_cost[MAXN]; // i 号药水的最小花费是否已经定型（已从堆中弹出并确定）
long long ways[MAXN]; // 最小花费对应的方案数
int recipe_cnt; // 已读入的配方数
int rec_a[MAXR]; // 配方原料 A
int rec_b[MAXR]; // 配方原料 B
int rec_c[MAXR]; // 配方产物 C
vector<int> by_potion[MAXN]; // by_potion[u]：把 u 当原料的配方编号
vector<int> by_result[MAXN]; // by_result[c]：产出 c 的配方编号
// 第一阶段：用「两个原料都定型」的 Dijkstra 求出每个药水的最小花费
void build_min_cost() {
priority_queue<pair<long long, int>, vector<pair<long long, int>>,
greater<pair<long long, int>>>
heap; // (花费, 药水编号)，花费在前才能按它比大小
for (int i = 0; i < n; i++) {
cost[i] = price[i]; // 初始候选就是「直接买」
fixed_cost[i] = false;
heap.push({cost[i], i});
}
while (!heap.empty()) {
long long cur = heap.top().first;
int u = heap.top().second;
heap.pop();
if (fixed_cost[u] || cur != cost[u]) continue; // 已定型，或堆里是更贵的旧记录
fixed_cost[u] = true;
for (int idx : by_potion[u]) {
int a = rec_a[idx];
int b = rec_b[idx];
int c = rec_c[idx];
// 另一种原料也必须定型；若 A、B 是同一种药水，它自己定型就够了
int other = (a == b) ? a : (a == u ? b : a);
if (!fixed_cost[other]) continue;
long long candidate = cost[a] + cost[b];
if (candidate < cost[c]) {
cost[c] = candidate;
heap.push({candidate, c});
}
}
}
}
// 第二阶段：按最小花费升序累计方案数
void count_ways() {
vector<pair<long long, int>> order; // (最小花费, 药水编号)
for (int i = 0; i < n; i++) order.push_back({cost[i], i});
// 最优配方的两个原料花费都严格小于产物，所以按花费升序就能保证原料先算完；
// 花费相同的药水之间不可能互为原料，因此同花费的先后顺序不影响结果
sort(order.begin(), order.end());
for (const auto& item : order) {
int u = item.second;
long long total = (price[u] == cost[u]) ? 1 : 0; // 直接买一份
for (int idx : by_result[u]) {
int a = rec_a[idx];
int b = rec_b[idx];
if (cost[a] + cost[b] == cost[u]) {
// 两个原料的选法互相独立，用乘法原理组合；方案总数不超过 2^63-1，不会溢出
total += ways[a] * ways[b];
}
}
ways[u] = total;
}
}
void read_input() {
cin >> n;
for (int i = 0; i < n; i++) cin >> price[i];
// 配方行以空行结束，用 cin 读到 EOF 即可
int a, b, c;
while (cin >> a >> b >> c) {
recipe_cnt++;
rec_a[recipe_cnt] = a;
rec_b[recipe_cnt] = b;
rec_c[recipe_cnt] = c;
by_potion[a].push_back(recipe_cnt);
if (b != a) by_potion[b].push_back(recipe_cnt); // 同一种原料只登记一次
by_result[c].push_back(recipe_cnt);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
build_min_cost();
count_ways();
cout << cost[0] << ' ' << ways[0] << '\n';
return 0;
}复杂度
最短成本约 O((n+r)log n)，计数 O(n log n+r)，空间 O(n+r)。
总结
普通图只能表达「或」，配方需要「与」，所以它属于超图：{A,B} → C 是一条尾巴挂两个节点的超边，长度是两者成本之和。因为价格为正，超边长度严格大于任一尾部的成本，Dijkstra 的定型论证得以保留，只需把触发条件从「前驱到了」换成「所有前驱都到了」。