Codeforces 1343E Weights Distributing【分配边权的两段最短路】

题目

You are given an undirected unweighted graph consisting of n vertices and m edges (which represents the map of Bertown) and the array of prices p of length m. It is guaranteed that there is a path between each pair of vertices (districts).

Mike has planned a trip from the vertex (district) a to the vertex (district) b and then from the vertex (district) b to the vertex (district) c. He can visit the same district twice or more. But there is one issue: authorities of the city want to set a price for using the road so if someone goes along the road then he should pay the price corresponding to this road (he pays each time he goes along the road). The list of prices that will be used p is ready and they just want to distribute it between all roads in the town in such a way that each price from the array corresponds to exactly one road.

You are a good friend of Mike (and suddenly a mayor of Bertown) and want to help him to make his trip as cheap as possible. So, your task is to distribute prices between roads in such a way that if Mike chooses the optimal path then the price of the trip is the minimum possible. Note that you cannot rearrange prices after the start of the trip.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 \le t \le 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains five integers n, m, a, b and c (2 \le n \le 2 \cdot 10^5, n-1 \le m \le min(\frac{n(n-1)}{2}, 2 \cdot 10^5), 1 \le a, b, c \le n) — the number of vertices, the number of edges and districts in Mike's trip.

The second line of the test case contains m integers p_1, p_2, \dots, p_m (1 \le p_i \le 10^9), where p_i is the i-th price from the array.

The following m lines of the test case denote edges: edge i is represented by a pair of integers v_i, u_i (1 \le v_i, u_i \le n, u_i \ne v_i), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair (v_i, u_i) there are no other pairs (v_i, u_i) or (u_i, v_i) in the array of edges, and for each pair (v_i, u_i) the condition v_i \ne u_i is satisfied. It is guaranteed that the given graph is connected.

It is guaranteed that the sum of n (as well as the sum of m) does not exceed 2 \cdot 10^5 (\sum n \le 2 \cdot 10^5, \sum m \le 2 \cdot 10^5).

Output

For each test case, print the answer — the minimum possible price of Mike's trip if you distribute prices between edges optimally.

题目大意

给你一个 n 个点 m 条边的无向无权图,一个长度为 m 的数组 p,以及三个地点 A,B,C

现在你可以任意将 p_1\dots p_m 一一对应给每一条边作为边权,问你 A\rightarrow B\rightarrow C 的最短路径是多少

题解

首先考虑简化版题目:问你 A\rightarrow B 的最短路径是多少

显然有贪心做法:从 AB bfs找出最短路长度为 k,然后将 p_1\dots p_m 中的最小的 k 个值加起来就是答案

但是原题中要考虑到一个问题,就是如果两次的最短路有重复的边,这就意味着可以将某个较小的 p 值重复利用两次以减小答案。所以,原贪心做法gg

现在考虑两条路径有重合,最优答案是一个怎样的形态?

先说结论:一定有一个中间点 D,最优答案为 A\rightarrow D \rightarrow B \rightarrow D \rightarrow C,也就是 BD 段重复了

证明?

证明有且只有BD段这一段是重复的:如果有两段重复,则将这两段中间的两个支路的其中一段也作为重复段,一定使答案更优

证明重复段一定与 B 相连:如果经历了重复段后,还要分别走两个支路才能在 B 汇合,则将其中一个支路作为重复段一定使答案更优

证毕。(说这么啰嗦其实就是懒得画图了

所以做法就是,先分别从 A,B,C bfs单源最短路一下,然后枚举中间点,取最小答案即可

Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX_N 200005
#define MAX_M 200005
#define INF 0x3f3f3f3f3f3f3f3fLL
#define pii pair<int, int>
#define int long long

using namespace std;

int T, n, m, A, B, C;
int p[MAX_M];
int da[MAX_N];
int db[MAX_N];
int dc[MAX_N];
vector<int> e[MAX_N];
queue<int> q;

void bfs(int *dis, int s) {
    memset(dis, 0x3f, sizeof(int) * (n + 5));
    dis[s] = 0, q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < e[x].size(); i++) {
            int t = e[x][i];
            if (dis[t] >= INF) {
                dis[t] = dis[x] + 1, q.push(t);
            }
        }
    }
}

int getsum(int x, int y) {
    if (x > y) {
        return 0;
    }
    return p[y] - p[x - 1];
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld%lld%lld%lld", &n, &m, &A, &B, &C);
        for (int i = 1; i <= m; i++) {
            scanf("%lld", p + i);
        }
        sort(p + 1, p + 1 + m);
        for (int i = 1; i <= m; i++) {
            p[i] += p[i - 1];
        }
        int x, y;
        for (int i = 1; i <= n; i++) {
            e[i].clear();
        }
        for (int i = 1; i <= m; i++) {
            scanf("%lld%lld", &x, &y);
            e[x].push_back(y);
            e[y].push_back(x);
        }
        bfs(da, A);
        bfs(db, B);
        bfs(dc, C);
        int ans = INF;
        for (int i = 1; i <= n; i++) {
            if (db[i] + da[i] + dc[i] <= m) {
                ans = min(ans, (getsum(1, db[i]) << 1) + getsum(db[i] + 1, db[i] + da[i] + dc[i]));
            }
        }
        printf("%lld\n", ans);
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注