对配方超边做 Dijkstra 式松弛，再按最小成本递增顺序统计最优方案数。
OJ: luogu
题目 ID: P1875
难度:提高
标签:最短路Dijkstra计数python
日期: 2026-07-17 03:00
题意
药水可直接购买，也可由两份药水合成；求 0 号药水最小成本和最优方案数。
思路
初始距离是购买价格。某原料成本确定或下降时，检查包含它的配方 A+B->C，用 cost[A]+cost[B] 松弛 C。最小成本确定后，最优配方的原料成本都严格小于成品，按成本排序即可从低到高统计购买方案和合成方案。
Python 知识
- EOF 输入用
read().split()，每三个整数切成一个配方元组。 heapify一次把所有购买方案放入堆。- 生成器求和表达
ways[A]*ways[B]的配方组合数。
代码
python
import sys
from heapq import heapify, heappop, heappush
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
price = data[1:n + 1]
recipes = [tuple(data[index:index + 3]) for index in range(n + 1, len(data), 3)]
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)
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]
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]
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-07-17 01:40
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
最短成本约 O((n+r)log n)，计数 O(n log n+r)，空间 O(n+r)。
总结
二元配方是“两个前驱同时到齐”的超边，仍可用单调成本顺序处理。