CodeForces 1343E Weights Distributing

题意

多组样例

给定$n,m,a,b,c$，给定一个长度为$m$的数组$p[]$，给定$m$条边，构成一个$n$个点$m$条边的无向图，$Mike$想要从$a$走到$b$，再从$b$走到$c$，你可以在他从$a$出发前将$p[]$中的值分配到$m$条边上，问$Mike$最少走多少路程

分析

我们先将所有边的权值赋为$1$，意为两点间的最小边数为多少

如果$a$到$b$和$b$到$c$的最短路不重合，那就直接将两条路上的边从小到大赋值即可，问题在于有重合的部分路径

发现$\sum n\leq 2\cdot 10^5$，我们可以枚举重合的点$i$，让$Mike$走路径$a->i->b->i->c$，然后求得边数，其中$i->b$的路径为$p[]$中最小的几个元素，因为要走两遍，$i->a$和$i->c$的的路径为剩下元素中最小的元素

由于为无向图，$i$到三点距离即为三点到$i$距离，为表述方便，皆用$i$到三点表述

枚举$i$肯定不能以$i$为起点求最短路，否则时间复杂度太高，则可以以三点求最短路，然后枚举$i$

先计算$i->a$的边数，以$a$为起点，使用$Dijkstra$算法，再计算$i->b$的边数，以$b$为起点，使用$Dijkstra$算法，再计算$i->c$的边数，以$c$为起点，使用$Dijkstra$算法，其中不同的距离设为$disa[],disb[],disc[]$

因为是求路径权值和，可直接排序后计算前缀和$sum[]$

设$i->a$的路径为$disai$，$i->$的b路径为$disbi$，$i->c$的路径为$disci$，则答案为$sum[disai + disbi + disci] + sum[disbi]$的最小值(三边总的前缀和加上$i->b$的二次计算)

由于$i$到三点的路径不可能有重叠（否则取重叠点可使得答案更小），因此三条路径和小于$m$，正好使得$disai + disbi + disci$不会超出$sum[]$的范围

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
const int maxn = (ll) 2e5 + 5;
const int mod = (ll) 1e9 + 7;
const int inf = 0x3f3f3f3f;
int T = 1;

struct edge {
    int v, next, w;
} e[maxn << 1];

struct node {
    int dis, u;

    bool operator<(const node &b) const {
        return dis > b.dis;
    }
};

int cnt;
int head[maxn];
int disa[maxn];
int disb[maxn];
int disc[maxn];
bool vis[maxn];

void addedge(int u, int v, int w) {
    e[++cnt].next = head[u];
    e[cnt].v = v;
    e[cnt].w = w;
    head[u] = cnt;
    e[++cnt].next = head[v];
    e[cnt].v = u;
    e[cnt].w = w;
    head[v] = cnt;
}

int n, m, s;

void dijkstra_a() {
    priority_queue<node> q;
    disa[s] = 0;
    node st;
    st.dis = 0;
    st.u = s;
    q.push(st);
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (vis[u.u])
            continue;
        vis[u.u] = true;
        for (int i = head[u.u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if (disa[v] > disa[u.u] + e[i].w) {
                disa[v] = disa[u.u] + e[i].w;
                node w;
                w.dis = disa[v];
                w.u = v;
                q.push(w);
            }
        }
    }
}

void dijkstra_b() {
    priority_queue<node> q;
    disb[s] = 0;
    node st;
    st.dis = 0;
    st.u = s;
    q.push(st);
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (vis[u.u])
            continue;
        vis[u.u] = true;
        for (int i = head[u.u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if (disb[v] > disb[u.u] + e[i].w) {
                disb[v] = disb[u.u] + e[i].w;
                node w;
                w.dis = disb[v];
                w.u = v;
                q.push(w);
            }
        }
    }
}

void dijkstra_c() {
    priority_queue<node> q;
    disc[s] = 0;
    node st;
    st.dis = 0;
    st.u = s;
    q.push(st);
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (vis[u.u])
            continue;
        vis[u.u] = true;
        for (int i = head[u.u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if (disc[v] > disc[u.u] + e[i].w) {
                disc[v] = disc[u.u] + e[i].w;
                node w;
                w.dis = disc[v];
                w.u = v;
                q.push(w);
            }
        }
    }
}

int num[maxn], sum[maxn];

void solve() {
    memset(head, -1, sizeof(head));
    cnt = 0;
    int a, b, c;
    cin >> n >> m >> a >> b >> c;
    rep(i, 1, m)cin >> num[i];
    sort(num + 1, num + 1 + m);
    rep(i, 1, m)sum[i] = sum[i - 1] + num[i];
    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        addedge(u, v, 1);
    }
    s = a;
    rep(i, 1, n) {
        disa[i] = disb[i] = disc[i] = inf;
        vis[i] = false;
    }
    dijkstra_a();
    s = b;
    rep(i, 1, n)vis[i] = false;
    dijkstra_b();
    s = c;
    rep(i, 1, n)vis[i] = false;
    dijkstra_c();
    int ans = LLONG_MAX;
    rep(i, 1, n) {
        int disai = disa[i];
        int disbi = disb[i];
        int disci = disc[i];
        if (disai + disbi + disci > m)
            continue;
        int now = sum[disai + disbi + disci] + sum[disbi];
        ans = min(ans, now);
    }
    cout << ans << '\n';
}


signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}