CF1343E. Weights Distributing（最短路 枚举 思维）

CF1343E. Weights Distributing（最短路 枚举 思维）

​​linkk​​

题意：

思路：

代码：

// Problem: E. Weights Distributing// Contest: Codeforces - Codeforces Round #636 (Div. 3)// URL: Memory Limit: 256 MB// Time Limit: 2000 ms// // Powered by CP Editor (namespace std;typedef long long ll;typedef unsigned long long ull;typedef pairPLL;typedef pairPII;typedef pairPDD;#define I_int llinline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}#define read read()#define rep(i, a, b) for(int i=(a);i<=(b);++i)#define dep(i, a, b) for(int i=(a);i>=(b);--i)ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}const int maxn=2e5+7,maxm=1e6+7,mod=1e9+7;ll n,m,a,b,c,val[maxn];vectorg[maxn];ll da[maxn],db[maxn],dc[maxn];void init(){ rep(i,1,n) g[i].clear();}void bfs(int s,ll dis[]){ rep(i,1,n) dis[i]=1e18; queueq; q.push(s);dis[s]=0; while(!q.empty()){ int t=q.front();q.pop(); for(int tt:g[t]){ if(dis[tt]>dis[t]+1){ dis[tt]=dis[t]+1; q.push(tt); } } }}int main(){ int _=read; while(_--){ n=read,m=read,a=read,b=read,c=read; init(); rep(i,1,m) val[i]=read; sort(val+1,val+1+m); rep(i,1,m) val[i]+=val[i-1]; rep(i,1,m){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } bfs(a,da); bfs(b,db); bfs(c,dc); ll ans=1e18; for(int i=1;i<=n;i++){ //cout<m) continue; ans=min(ans,val[db[i]]+val[da[i]+db[i]+dc[i]]); } printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。