37. CF-Weights Distributing

链接

这是一个比较经典的题目。容易想到求出两段路径重合的部分，然后贪心的放权值。那么跑三次最短路，枚举重合部分的端点即可。

正解没什么好说的。这题有趣的地方在于，如果数据比较弱，可能会把一些错误做法放过去。

一种错误做法是：只求 $a$ 点和 $c$ 点的单源最短路，然后在枚举端点的时候，认为端点一定在 $a,b$ 或者 $b,c$ 之间的最短路径上。这个结论是错误的，可以构造出这样的反例：

7 8 1 4 6
1 2 3 4 100 100 100 100
1 2
2 3
3 4
3 5
5 6
3 7
1 7
6 7

这里的答案显然是 $13$，而错误做法可能会得到 $111$。

这种构造的依据是最短路并不是唯一的。然而，即便最短路是唯一的，上面的做法依然不正确。不妨设 $a,b$ 与 $b,c$ 两条最短路径共用了从点 $m$ 到点 $b$ 的路径，$m$ 到 $a,b,c$ 三个点的距离分别为 $100,10,100$，而在这两条路径外面有一个点 $n$，它到三个点的距离分别为 $90,30,90$，那么这个 $n$ 点在上面的做法中是不会被遍历到的，但只需设计好权值，就可以使最优解经过这个点。

下面是正解的代码，最短路用 BFS 实现更好。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
const int maxn = 2e5 + 5;
const ll inf = 1e18;
vector<int> g[maxn];
void solve() {int n, m, A, B, C;cin >> n >> m >> A >> B >> C;vector<ll> w(m);for (auto& i : w) cin >> i;for (int i = 1, u, v; i <= m; ++i) {cin >> u >> v;g[u].pb(v);g[v].pb(u);}sort(w.begin(), w.end());vector<int> disA(n + 1, 0x3f3f3f3f);vector<int> disB(n + 1, 0x3f3f3f3f);vector<int> disC(n + 1, 0x3f3f3f3f);vector<int> p(n + 1);function<void(int, vector<int>&)> dijkstra = [&](int s, vector<int>& d) {vector<int> vis(n + 1, 0);struct node {int id, dis;bool operator < (const node& rhs) const {return (dis == rhs.dis ? id > rhs.id : dis > rhs.dis);}};priority_queue<node> q;d[s] = 0;q.push({ s, 0 });while (!q.empty()) {auto [cur, cost] = q.top();q.pop();if (vis[cur]) continue;vis[cur] = 1;d[cur] = cost;for (auto to : g[cur]) {if (vis[to]) continue;if (d[to] > d[cur] + 1) {d[to] = d[cur] + 1;q.push({ to, d[to] });p[to] = cur;}}}};vector<ll> pre(m + 1, 0);for (int i = 1; i <= m; ++i) {pre[i] = pre[i - 1] + w[i - 1];}dijkstra(A, disA);dijkstra(B, disB);dijkstra(C, disC);ll ans = inf;for (int i = 1; i <= n; ++i) {int da = disA[i], db = disB[i], dc = disC[i];if (da + db + dc > m) continue;ans = min(ans, pre[db] + pre[da + db + dc]);}cout << ans << endl;for (int i = 1; i <= n; ++i) {g[i].clear();}
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;cin >> T;while (T--) {solve();}return 0;
}