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{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;
}
