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;
    }
}

/**
**/