题解：CF1343E Weights Distributing

· · 题解

定义 dis(i,j) 表示从 i 走到 j 的最少边数。

假设 a \sim b 与 b \sim c 的路径没有重合的话，那么只需要 p 中最小的 dis(a,b)+dis(b,c) 个数值，将它们赋到 a \sim b 和 b \sim c 的路径上就可以了。

但是现在的问题就在于路径重合的问题，如果还按照刚才的算法会把答案算大，甚至找到不存在的路径（即 dis(a,b)+dis(b,c) \gt m 的清空）。

考虑枚举重合信息。

枚举 md 作为 b 到 c 的路径上最后一个与 a \sim b 路径重合的节点。

那么，此时路径将分为三个部分：

此时按照最优方式，上述三段路径都按照最短路计算就可以了，即路径长度分别为 dis(a,md),dis(md,b),dis(md,c)。

然后，优先把 p 中较小的数值分配给第二部分的路径，然后再分配一，三部分的路径就行了。

尽管有可能因此不再满足路径重合的一些条件，但是这仍然是对的，由于以下两点：

对于最短路的计算，bfs 预处理 a,c 到其他所有点的最小边数就可以了。 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=2e5+5;
int n,m,a,b,c;
ll p[maxn],pre[maxn];
ll w(int l,int r){
    return pre[r]-pre[l-1];
}
vi g[maxn];
int disa[maxn],disb[maxn],disc[maxn];
void bfs(int s,int* dis){
    FOR(i,1,n)dis[i]=1e9;
    queue<int> q;
    q.push(s);
    dis[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int& v:g[u]){
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
}
void clear(){
    FOR(i,1,n){
        g[i].clear();
    }
}
void solve(int id_of_test){
    read(n);
    read(m);
    read(a);
    read(b);
    read(c);
    FOR(i,1,m){
        read(p[i]);
    }
    sort(p+1,p+m+1);
    FOR(i,1,m){
        pre[i]=pre[i-1]+p[i];
    }
    FOR(i,1,m){
        int u,v;
        read(u);
        read(v);
        g[u].eb(v);
        g[v].eb(u);
    }
    bfs(a,disa);
    bfs(b,disb);
    bfs(c,disc);
    ll ans=1e18;
    FOR(mid,1,n){
        // a-->b
        // b-->c
        // 上述路径共同都要到达 mid
        int len=disb[mid];
        if(len+disa[mid]+disc[mid]>m)continue;
        ll res=pre[len]*2;
        res+=w(len+1,len+disa[mid]+disc[mid]);
    //    printf("mid = %d res = %lld\n",mid,res);
        ckmn(ans,res);
    }
    printf("%lld\n",ans);
    clear();
}
int main()
{
    int T;
    read(T);
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}
/*
1. 对题意的理解能否和样例对的上？  
2. 每一步操作，能否和自己的想法对应上？  
3. 每一步操作的正确性是否有保证？  
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？  
*/