专栏文章
题解:CF1343E Weights Distributing
CF1343E题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miq2u128
- 此快照首次捕获于
- 2025/12/03 22:02 3 个月前
- 此快照最后确认于
- 2025/12/03 22:02 3 个月前
CF1343E Weights Distributing
Problem
给出一个有 个点, 条边的无向图和一个长为 的权值序列 。
你可以随意安排边权(每条边权对应 中的一个数,不可以重复)。
求 到 的最短路与 到 的最短路的和的最小值。
。
Sol
发现最后这两条路径的交一定可以是一段路径。所以枚举 和 的交 。然后这一段重复经过的边的权都放比较小的。对 排序之后做前缀和,然后分别以 为源点跑最短路即可,然后这里只需要知道边的数量,所以可以直接 01BFS 做到 。
Code
CPP#include <bits/stdc++.h>
using namespace std;
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define ll long long
#define vi vector<int>
#define pb emplace_back
#define sz(a) ((int) a.size())
#define pii pair<int, int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, A, B, C;
int a[200005];
ll s[200005];
vi e[200005];
int dis[3][200005];
void Dijkstra(int s, int *dis) {
queue<int> que;
memset(dis, 0x3f, (n + 1) * sizeof (int));
que.emplace(s);
dis[s] = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int v : e[u])
if (dis[v] == inf)
dis[v] = dis[u] + 1, que.emplace(v);
}
}
void Solve() {
scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
L(i, 1, m) scanf("%d", &a[i]);
sort(a + 1, a + m + 1);
L(i, 1, m) s[i] = a[i] + s[i - 1];
L(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
e[u].pb(v), e[v].pb(u);
}
Dijkstra(A, dis[0]);
Dijkstra(B, dis[1]);
Dijkstra(C, dis[2]);
ll ans = INF;
L(i, 1, n) {
ll c0 = dis[0][i];
ll c1 = dis[1][i];
ll c2 = dis[2][i];
if (c0 + c1 + c2 > m) continue;
ans = min(ans, s[c0 + c1 + c2] + s[c1]);
}
printf("%lld\n", ans);
L(i, 1, n) e[i].clear();
}
int main() {
int T;
scanf("%d", &T);
while (T--)
Solve();
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...