Codeforces Round #636 (Div. 3) - E. Weights Distributing（BFS，贪心）

Codeforces Round #636 (Div. 3) 全文见：https://editor.csdn.net/md/?articleId=112727618

E. Weights Distributing

题意：给定一个无向图。给定一个权值数组。要把权值分配到每条边上，使得从a到b再到c经过的总边权和最小。

思路：显然，把最小的权值分配到最短路径上就是最优解。考虑一个朴素的想法。就是先求a-b的最短路径。然后把小权值分配上去。再求b-a的最短路径，把剩下最小的边权分配上去。但是这样肯定是不对的。如下图：这种策略下，如果要从6到1再到8。那么肯定不会选择到 3 -> 8这条边。 但是实际上，如果绕远路从 1-2-3-8 实际上会比 1-7-8 更优。所以不能直接这样贪心。 有可能有的边会走两遍。那就要去枚举，哪些边会走两遍，或者说枚举哪些点作为中继点，也就是说 a-d-b-d-c。枚举这个d。那么这个d肯定是在某一条最短路径上的点。所以要先找出所有 可能在最短路径上的点。然后以这些点作为中继。但是还要枚举两遍。有可能是在 a-b 的最短路径上的点作为中继。也有可能是 b-c最短路径上的点作为中继。取最小。才是正确答案。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define mk make_pair
#define gcd __gcd
#define pb push_back
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 1e6+7;
int n,m,k,t = 1,cas = 1;
//int a[N],b[N];
struct node{
    int from,to,dis;
    node(int a,int b,int c):from(a),to(b),dis(c){}
};
vector<node> que;
int dis1[N];
int dis2[N];
int cost[N];
int onpath[N];
bool mark[N];
vector<int> edge[N];

void bfs(int s,int t,int dis[]){
    for(int i = 0 ; i <= n ; i ++) mark[i] = 0;
    mark[s] = 1;
    int pos = 0;
    que.pb(node(-1,s,0));
    while(pos < que.size()){
        node now = que[pos++];
        dis[now.to] = now.dis;
        for(int i = 0; i < edge[now.to].size();i ++){
            int to = edge[now.to][i];
            if(!mark[to]){
                mark[to] = 1;
                que.pb(node(pos-1,to,now.dis+1));
            }
        }
    }
    que.clear();
}

int solve(int a,int b,int c){
    for(int i = 1 ; i <= n ; i ++)
        onpath[i] = 0;
    bfs(a,b,dis1);
    int dis_ab = dis1[b];
    bfs(b,a,dis2);
    for(int i = 1 ; i <= n ; i ++)
        if(dis1[i]+dis2[i] == dis_ab)
            onpath[i] = 1;
    bfs(c,b,dis2);
    int res = cost[dis_ab];
    int minn = 1e18;
    for(int i = 1; i <= n; i ++){
        if(!onpath[i]) continue;
        if(dis1[i] > dis_ab) continue;
        if(dis2[i]+dis_ab > m) continue;
        int new_cost = cost[dis_ab-dis1[i]] + (cost[dis2[i]+dis_ab]-cost[dis_ab]);
        //cout<<i<<" "<< dis1[i]<<" "<<dis2[i]<<" "<<(cost[dis2[i]+dis_ab]-cost[dis_ab])<<" "<<new_cost<<endl;
        minn = min(minn,new_cost);
    }
    return res+minn;
}

signed main(){
    cin>>t;
    while(t--){
        int a,b,c;
        cin>>n>>m>>a>>b>>c;
        for(int i = 1 ; i <= n ; i ++)
            edge[i].clear();
        for(int i = 1 ; i <= m ; i ++)  cin>>cost[i];
        sort(cost+1,cost+m+1);
        for(int i = 2 ; i <= m ; i ++)
            cost[i] += cost[i-1];
        for(int i = 0 ; i < m ; i ++){
            int x,y;
            cin>>x>>y;
            edge[x].pb(y);
            edge[y].pb(x);
        }
        cout<<min(solve(a,b,c),solve(c,b,a))<<endl;
    }
}

/**
**/