题解：P12780 [ICPC 2024 Yokohama R] Omnes Viae Yokohamam Ducunt?

· · 题解

妙妙推导题。

首先思考假设我们建了一个最小生成树，那么对于任意一条从 i 到首都的路径中的边 e，如果断开那么 i 绝对到不了首都，所以 i 其实是给任意一条从 i 到首都的路径中的边都增加了 p_i 的“贡献”，所以，题目所求就是（P(e) 指的是 e 的损失，C(e) 指的是 e 的脆弱度，D(i) 指的是从 i 到首都 1 的距离（以脆弱度为边））：

\sum_e P(e) \times C(e) =\sum_i p_i \times D(i)

等等，这不就是……最短路吗？

是的，于是这道题就没了。

十年 OI 一场空，不开 long long 见祖宗！！

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node
{
    int x;
    long long w;
    bool operator<(const node&a)const
    {
        return w>a.w;
    }
};
int a[N];
vector<node>e[N];
priority_queue<node>q;
long long d[N];
int vis[N];
signed main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i = 1;i<=m;i++)
    {
        int x,y;
        long long z;
        scanf("%d %d %lld",&x,&y,&z);
        e[x].push_back({y,z});
        e[y].push_back({x,z});
    }
    memset(d,0x3f,sizeof(d));
    q.push({1,0});
    d[1] = 0;
    while(q.size())
    {
        int x = q.top().x;
        q.pop();
        if(vis[x])
        {
            continue;
        }
        vis[x] = 1;
        for(node v:e[x])
        {
            if(d[x]+v.w<d[v.x])
            {
                d[v.x] = d[x]+v.w;
                q.push({v.x,d[v.x]});
            }
        }
    }
    long long ans = 0;
    for(int i = 1;i<=n;i++)
    {
        ans+=(long long)a[i]*d[i];
    }
    printf("%lld",ans);
    return 0;
}