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