CF1343E Weights Distributing 题解

题目链接：CF1343E Weights Distributing

题意：

给出一个有 \(n\) 个点，\(m\) 条边的无向图和一个长为 \(m\) 的权值序列 \(w\)。

你可以随意安排边权（每条边权对应 \(w\) 中的一个数，不可以重复）。

求 \(a\) 到 \(b\) 的最短路与 \(b\) 到 \(c\) 的最短路的和的最小值。

输入格式：

多组数据。每次给出 \(n,m,a,b,c\) 。第一行给出 \(n\) 个整数 \(w_i\) 。接下来 \(m\) 行给出边 \((u,v)\) 。

输出格式：

对于每组数据，输出最小值。

数据范围：

\(1\le n-1 \le m \le \min\left\{\frac{n(n-1)}{2},~2\times 10^5\right\},~1 \le \sum n,\sum m \le 2 \times 10^5,~ 1 \le w_i \le 10^9\) 。

注意到 \(a\leadsto b\) 和 \(b \leadsto c\) 的最短路径可能重合，会有一些边被算两遍。

根据贪心的思想，我们会优先把小的边分配给他们。

但是这个重合的路径怎么找呢？

一个错误的做法是直接找两条最短路径的交集，反例懒得构造，很容易卡。

答案是枚举一个 \(d\) ，然后答案就是 \[ \mathtt{dis}(a,d) + 2\times\mathtt{dis}(b,d) + \mathtt{dis}(d,c) \] 因为边权是可以自己加的，所以我们用 \(\mathtt{bfs}\) 把边权当成 \(1\) 预处理一下最少经过几条边啥的，具体看代码。

单组数据时间复杂度 \(\mathcal{O}(n + m \log m)\) ，瓶颈在排序。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

int n,m,A,B,C,pos=1,head[N],w[N],sum[N],da[N],db[N],dc[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
queue<int> q;
void solve(int st,int *d)
{
    for(int i=1; i<=n; i++) d[i] = INF;
    d[st] = 0; while(!q.empty()) q.pop();
    for(q.push(st); !q.empty(); )
    {
        int u = q.front(); q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            if(d[v] == INF) { d[v] = d[u] + 1; q.push(v); }
        }
    }
}
void clear()
{ pos = 1; for(int i=1; i<=n; i++) head[i] = 0; }
void work()
{
    clear(); cin >> n >> m >> A >> B >> C;
    for(int i=1; i<=m; i++) cin >> w[i];
    sort(w + 1, w + 1 + m);
    for(int i=1; i<=m; i++) sum[i] = sum[i-1] + w[i];
    for(int i=1,u,v; i<=m; i++)
    { cin >> u >> v; addEdge(u,v); addEdge(v,u); }
    solve(A,da); solve(B,db); solve(C,dc);
    int res = INF;
    for(int i=1,a,b,c; i<=n; i++)
    {
        a = da[i], b = db[i], c = dc[i];
        if(a + b + c <= m) down(res, sum[a + b + c] + sum[b]);
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q; cin >> _Q; while(_Q--) work();
    return 0;
}