Weights Distributing
题目链接:https://codeforces.com/problemset/problem/1343/E
题意:
给你一个 N 个点 M 条边以及三个目的地 A、B、C,你需要从 A→B→C
现在你可以重新排列边的权值,问从A→B→C的最短路径是多少?
分析:
不难发现 A→B→C 可以转换成 A→X→B→X→C , X∈[1 , N]
我们可以先进行3次 BFS 求出每个点分别到A , B , C的距离disA[i],disB[i],disC[i]
然后枚举 x , 那么答案 ans = min(ans , disA[x] + disB[x] + disB[x] + disC[x])
其中disB[x]走了两次,所以尽量把边权小的边分配给disB[x],然后再到disA[x],disC[x]
对于 disA[x] + 2 * disB[x] + disC[x] 我们可以通过维护前缀和 O(1) 计算
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define int long long #define fi first #define se second using namespace std; template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} const int inf (0x3f3f3f3f); const int N = 3e5 + 10; struct Edge{ int nex , to; }edge[N << 1]; int head[N] , tot; void add_edge(int u , int v) { edge[++ tot].nex = head[u]; edge[tot].to = v; head[u] = tot; } int dis1[N] , dis2[N] , dis3[N] , vis[N]; int w[N] , n , m , a , b , c; pair<int , int>pa; void bfs(int st , int *dis) { rep(i , 0 , n) vis[i] = 0 , dis[i] = inf; dis[st] = 0 , vis[st] = 1; queue<pair<int , int>>que; que.push(make_pair(st , 0)); while(!que.empty()) { pair<int , int> now = que.front(); que.pop(); int u = now.fi , w = now.se; for(int i = head[u] ; i ; i = edge[i].nex) { int v = edge[i].to; if(vis[v]) continue ; vis[v] = 1; dis[v] = w + 1; pair<int , int> ha = make_pair(v , w + 1); que.push(ha); } } } void init() { tot = 0; rep(i , 1 , n) head[i] = 0; } signed main() { int t; read(t); while(t --) { init(); read(n) , read(m) , read(a) , read(b) , read(c); rep(i , 1 , m) read(w[i]); rep(i , 1 , m) { int u , v ; read(u) , read(v); add_edge(u , v) ; add_edge(v , u) ; } sort(w + 1 , w + 1 + m); rep(i , 2 , m) w[i] += w[i - 1]; bfs(a , dis1) , bfs(b , dis2) , bfs(c , dis3); int ans = (0x3f3f3f3f3f3fll); rep(x , 1 , n) if(dis1[x] + dis2[x] + dis3[x] <= m) ans = min(ans , w[dis2[x]] + w[dis2[x] + dis1[x] + dis3[x]]); Out(ans) , puts(""); } return 0; }