P1875 佳佳的魔法药水

两个前置状态共同完成一次松弛

问题

P1875 佳佳的魔法药水
编号 $0$ 到 $n-1$ 的每种药水都可以直接购买，也可以按照若干配方把一份 $A$ 与一份 $B$ 合成为一份 $C$。初始没有任何药水，需要求得到 $0$ 号药水的最低花费，并统计操作步骤不同的所有最低花费方案。

数据规模：$1\le n\le1000$，购买价格位于 $[1,2.8\times10^4]$，方案数不超过 $2^{63}-1$。原题页面注明测试数据可能出现同一对原料对应不同产物的情况。

每种药水有两种情况，一种是直接购买，一种是由两瓶药合成。

为了得到最小的花费，我们可以使用小根堆来记录最小成本的药水。若某个原料确定后，枚举所有包含它的配方，若另一种原料也已经确定，就尝试用两者之和更新产物。

此时考虑方案数的更新，若得到更小的成本，方案数修改为两种原料方案数乘积；若是成本相等，则把这部分方案累加。

这个做法跟 Dijkstra 的堆优化很像，当配方的两个原料相同时，邻接关系只登记一次，避免同一配方被重复触发。所以这个做法可以看成 Dijkstra 在二元依赖上的扩展。

复杂度取决于配方枚举与堆操作，约为 $O((n+m)\log n)$。

本题的关键在于 “一次松弛需要两个已确定前置状态”。

▶

P1875

struct Edge { int a, b, c; };
vector<Edge> edges;
vector<int> adj[maxn];

struct State {
    int u; ll d;
    bool operator < ( const State &oth ) const {
        return d > oth.d;
    }
};

bool vis[maxn];
ll f[maxn];
ll dp[maxn];

void solve( ) {
    int n = read( );

    priority_queue<State> pq;
    for( int i = 0; i < n; ++ i ) {
        f[i] = read( );
        dp[i] = 1;
        pq.push({ i, f[i] });
    }

    int a, b, c;
    while( cin >> a >> b >> c ) {
        int id = edges.size( );
        edges.push_back({ a, b, c });
        adj[a].push_back( id );
        if( a == b ) continue;
        adj[b].push_back( id );
    } 

    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( );
        pq.pop( );
        if( vis[u] ) continue;
        if( f[u] != d ) continue;

        vis[u] = 1;

        for( int id : adj[u] ) {
            auto [a, b, c] = edges[id];
            if( !vis[a] || !vis[b] ) continue;

            int nd = f[a] + f[b];
            ll ways = dp[a] * dp[b];
            if( nd < f[c] ) {
                f[c] = nd;
                dp[c] = ways;
                pq.push({ c, f[c] });
            }
            else if( nd == f[c] ) {
                dp[c] += ways;
            }
        }
    }
    cout << f[0] << " " << dp[0] << '\n';
}