CF-636E Weights Distributing 题解

题目大意

给你一个n个点m条边的无向图，同时给你每条边的权值，你需要从a到b再到c，问你如何安排权值，使路径最短，求最短路径。

解题思路

可以分为两种情况

第一种情况，a，b，c之间没有重复，a->b->c。

第二种情况，a，b，c之间有重复的点，a->x->b->x->c。

其实两种情况是一样的，无论有没有重复的点，都可以使用第二种情况。

可以使用三个数组dis1[i]，dis2[i]，dis3[i]，分别来表示a，b，c到i节点最少需要走多少条边。

这样，这个题目就转变成了一个BFS的题目。

（搜索是真的不会，。。多练。。

将边权值从小到大排序后，可以使用前缀和，优化计算。

使用贪心的思想，因为b那段距离需要走两遍，所以优先给他最小的距离。

答案为num[dis1[i]+dis2[i]+dis3[i]]+num[dis2[i]]的最小值。

完整代码

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2e5 + 5;
int  vis[N], dis1[N], dis2[N], dis3[N];
long long num[N];
vector<int>v[N];

void bfs(int node,int dis[]) {
	memset(vis, 0, sizeof(vis));
	queue<int>q;
	q.push(node);
	vis[node] = 1;
	dis[node] = 0;
	while (q.size()) {
		int n = q.front();
		q.pop();
		for (auto x : v[n]) {
			if (!vis[x]) {
				q.push(x);
				vis[x] = 1;
				dis[x] = dis[n] + 1;
			}
		}
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, m, a, b, c;
		cin >> n >> m >> a >> b >> c;
		for (int i = 1; i <= n; i++)	v[i].clear();
		for (int i = 1; i <= m; i++)	cin>>num[i];
		for (int i = 1; i <= m; i++) {
			int l, r;
			cin >> l >> r;
			v[l].push_back(r);
			v[r].push_back(l);
		}
		sort(num + 1, num + 1 + m);
		for (int i = 1; i <= m; i++)	num[i] += num[i - 1];//前缀和
		bfs(a, dis1);
		bfs(b, dis2);
		bfs(c, dis3);
		long long ans = 1e18;//需要开long long，数据有点大		
		for (int i = 1; i <= n; i++) {
			if (dis1[i] + dis2[i] + dis3[i] > m)	continue;
            //如果需要走的边数大于m，直接continue
			ans = min(ans, num[dis1[i] + dis2[i] + dis3[i]] + num[dis2[i]]);
		}
		cout << ans << endl;
	}
}