CodeForces-1343E Weights Distributing

传送门：CodeForces-1343E

思路分析

枚举中转站x
a->x
x->b
b->x
x->c

那么这样重复的部分就是x->b
预处理前缀和，三次bfs计算出a，b，c到各个点的距离

样例输入

2
4 3 2 3 4
1 2 3
1 2
1 3
1 4
7 9 1 5 7
2 10 4 8 5 6 7 3 3
1 2
1 3
1 4
3 2
3 5
4 2
5 6
1 7
6 7

样例输出

7
12

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

vector<int>e[N];
int n,m,a,b,c;
ll da[N],db[N],dc[N],vis[N],val[N],s[N];

void bfs(int s,ll *dis){
    for(int i=0;i<=n;i++){
        vis[i]=0;
        dis[i]=INF;
    }
    dis[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto v:e[u]){
            if(dis[v]>dis[u]+1 && !vis[v]){
                dis[v]=dis[u]+1;
                vis[v]=1;
                q.push(v);
            }
        }
    }
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>a>>b>>c;
        for(int i=1;i<=n;i++) e[i].clear();
        for(int i=1;i<=m;i++) cin>>val[i];
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        sort(val+1,val+1+m);
        for(int i=1;i<=m;i++) s[i]=s[i-1]+val[i];
        bfs(a,da);
        bfs(b,db);
        bfs(c,dc);
        ll ans=2e18;
        for(int i=1;i<=n;i++){
            if(da[i]+db[i]+dc[i]>m) continue;
            ans=min(ans,s[db[i]]+s[da[i]+db[i]+dc[i]]);
        }
        cout<<ans<<endl;
        
    } 




    return 0;
}
&nbsp;