📝 题解：异兽合成的最小花费（最短路变形）

🔍 题意简述

游戏中有 $n$ 种异兽，每种异兽有原始售价 $p[i]$。另有 $m$ 条吞噬规则 $(a, b, c)$，表示：用一只种类 $a$ 和一只种类 $b$ 的异兽进行吞噬，可以合成出一只种类 $c$ 的异兽（$a$ 和 $b$ 消失）。

你可以进行两种操作：

1. 直接购买一只异兽，花费其原始价格；
2. 通过吞噬合成，消耗两只异兽，获得一只新异兽。

目标：对每种异兽 $i$，求出获得它的最小总花费。

💡 核心思想

这是一道最短路问题的变种，本质是：

某个异兽的最小花费，可以是它的原始价格，也可以是两个其他异兽花费之和（通过合成得到）。

例如：若规则为 $(1,2,7)$，则：

但更进一步，如果 $p[1]$ 或 $p[2]$ 本身也能通过其他合成得到更小的值，那它们的更新又会反过来影响 $p[7]$。

这形成了一个动态更新、相互依赖的优化过程，非常适合使用 Dijkstra 算法的松弛思想 来求解。

🔧 算法设计

我们将每种异兽视为一个节点，每条规则 $(a, b, c)$ 表示：

若已知 $p[a]$ 和 $p[b]$，则可用 $p[a] + p[b]$ 更新 $p[c]$。

由于合成不区分顺序（$a$ 吃 $b$ 和 $b$ 吃 $a$ 效果相同），我们为每条规则建立双向边：

• $a \rightarrow (b, c)$：表示用 $a$ 和 $b$ 可合成 $c$
• $b \rightarrow (a, c)$：表示用 $b$ 和 $a$ 可合成 $c$

然后使用优先队列（最小堆），按当前最小花费依次处理每个异兽：

• 每次取出当前花费最小的异兽 $u$；
• 遍历所有与 $u$ 相关的规则 $(u, v, c)$；
• 若 $p[u] + p[v] < p[c]$，则更新 $p[c]$，并将 $c$ 加入堆中，等待后续处理。

关键点：由于我们总是先处理花费最小的节点，因此每次松弛都是当前最优的，不会遗漏任何可能的更优路径。

✅ 为什么这个算法正确？

• 初始时，每个异兽的花费是其原始价格，这是上界。
• 每次通过合成，花费只会减小或不变，不会增大。
• 优先队列保证我们总是用“当前最小”的异兽去尝试更新其他节点。
• 每当一个节点的花费被更新，我们就将其重新入队，确保后续能继续传播最优值。
• 所有规则都会被充分松弛，直到无法再优化。

这与 Dijkstra 算法中“用最小距离节点松弛邻边”的思想完全一致，只是边权不再是固定值，而是“两个节点之和”。

📦 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+5;
const int inf=0x3f3f3f3f;

int n,m;
int p[N];
vector<pair<int,int> > e[N];

struct node
{
    int i;
    bool operator<(const node &other)const
    {
        return p[i]<p[other.i];
    }
};

void dij()
{
    priority_queue<node> q;
    for(int i=1;i<=n;i++) q.push({i});

    while(!q.empty())
    {
        int u=q.top().i;
        q.pop();

        for(auto i:e[u])
        {
            int b=i.first;
            int c=i.second;
            if(p[u]+p[b]<p[c])
            {
                p[c]=p[u]+p[b];
                q.push({c});
            }
        }
    }
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>p[i];

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e[a].push_back({b,c});
        e[b].push_back({a,c});
    }

    dij();

    for(int i=1;i<=n;i++)
        cout<<p[i]<<' ';
}

🧪 样例验证

输入1：

7 3
6 10 3 2 2 3 100
1 2 7
4 5 1
3 6 2

执行过程：

1. 初始：p = [6,10,3,2,2,3,100]
2. 用 (4,5,1) 更新：p[1] = min(6, 2+2)=4
3. 用 (3,6,2) 更新：p[2] = min(10, 3+3)=6
4. 用 (1,2,7) 更新：p[7] = min(100, 4+6)=10
5. 再次检查：所有更新稳定，无进一步优化。

输出：4 6 3 2 2 3 10 ✅