题解：CF1343E Weights Distributing
Pengzt
·
·
题解
CF1343E Weights Distributing
Problem
给出一个有 n 个点，m 条边的无向图和一个长为 m 的权值序列 w。
你可以随意安排边权（每条边权对应 w 中的一个数，不可以重复）。
求 a 到 b 的最短路与 b 到 c 的最短路的和的最小值。
###### Sol
发现最后这两条路径的交一定可以是一段路径。所以枚举 $a \leadsto b$ 和 $b \leadsto c$ 的交 $b \leadsto i$。然后这一段重复经过的边的权都放比较小的。对 $w$ 排序之后做前缀和，然后分别以 $a, b, c$ 为源点跑最短路即可，然后这里只需要知道边的数量，所以可以直接 01BFS 做到 $\mathcal{O}(n + m)$。
###### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define ll long long
#define vi vector<int>
#define pb emplace_back
#define sz(a) ((int) a.size())
#define pii pair<int, int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, A, B, C;
int a[200005];
ll s[200005];
vi e[200005];
int dis[3][200005];
void Dijkstra(int s, int *dis) {
queue<int> que;
memset(dis, 0x3f, (n + 1) * sizeof (int));
que.emplace(s);
dis[s] = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int v : e[u])
if (dis[v] == inf)
dis[v] = dis[u] + 1, que.emplace(v);
}
}
void Solve() {
scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
L(i, 1, m) scanf("%d", &a[i]);
sort(a + 1, a + m + 1);
L(i, 1, m) s[i] = a[i] + s[i - 1];
L(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
e[u].pb(v), e[v].pb(u);
}
Dijkstra(A, dis[0]);
Dijkstra(B, dis[1]);
Dijkstra(C, dis[2]);
ll ans = INF;
L(i, 1, n) {
ll c0 = dis[0][i];
ll c1 = dis[1][i];
ll c2 = dis[2][i];
if (c0 + c1 + c2 > m) continue;
ans = min(ans, s[c0 + c1 + c2] + s[c1]);
}
printf("%lld\n", ans);
L(i, 1, n) e[i].clear();
}
int main() {
int T;
scanf("%d", &T);
while (T--)
Solve();
return 0;
}
```