自动搬运

查看原文

来自洛谷，原作者为

	Cipher0128 ALL IN.

搬运于2025-08-24 22:13:19，当前版本为作者最后更新于2025-05-27 20:38:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

反复读完题后我们终于知道了要干什么：

建树，建虚树，求最值。

建树：在原图跑单源最短路，转移时特判距离相同取编号小者，并记录每个点从哪个点转移过来，最后找出最短路构成的树。

建虚树：回收区域是关键点，应拿它们建虚树，边权就是它们在回收路线上的距离。

求最值：用 $dp$ 求，设有节点 $x$，其子节点为 $y$，若 $y$ 被标记，这条路一定要被阻断，$x$ 的费用加上 $v_{x,y}$；否则可断可不断，$x$ 的费用加上 $v_{x,y}$ 与 $y$ 的费用的最小值。

代码：

#include<bits/stdc++.h>
#define rd read()
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
#define pb push_back
#define mkp make_pair
#define for_(a,b,c) for(int a=b;a<=c;++a)
#define For_(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
int n,m,S,Q,H;
const int N=4e5+10;
vector<pair<int,int>>vv[N],v[N],e[N];
struct node{
	int x,d;
};
priority_queue<node>q;
bool operator<(const node A,const node B){
	return A.d>B.d;
}
ll dis[N],id[N];
bool vis[N];
void dij() {
	memset(dis,0x3f,sizeof(dis));
	dis[S]=0;
	q.push({S,0});
	while(!q.empty()) {
		node h=q.top();
		q.pop();
		int x=h.x;
		if(vis[x])continue;
		vis[x]=1;
		for(auto h:vv[x]){
			int y=h.first,val=h.second;
			ll s=dis[x]+val;
			if(s<dis[y]){
				dis[y]=s;
				id[y]=x;
				q.push({y,dis[y]});
			}
			else if(s==dis[y]){
				id[y]=min(id[y],x);
			}
		}
	}
}
int st[N],tp;
ll P(ll x,ll y){
	return x*N+y;
}
unordered_map<ll,bool>mp;
int dep[N],dfn[N],td,f[N][30];
void dfs_LCA(int x){
	dfn[x]=++td;
	for(auto h:v[x]){
		int y=h.first,val=h.second;
		dep[y]=dep[x]+1;
		f[y][0]=x;
		dfs_LCA(y);
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	For_(i,H,0)if(dep[f[x][i]]>=dep[y])x=f[x][i];
	if(x==y)return x;
	For_(i,H,0)if(f[x][i]^f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
int num;
int k[N];
bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}
int a[N],tot;
int in[N];
int cntin;
bool flag;
ll DP(int x){
	if(in[x])flag=1;
	ll fx=0;
	for(auto h:e[x]){
		ll y=h.first,val=h.second;
		ll fy=DP(y);
		if(in[y])fx+=val;
		else fx+=min(val,fy);
	}
	e[x].clear();
	return fx;
}
void work(){
	k[++num]=S;
	sort(k+1,k+1+num,cmp);
	tot=0;
	for_(i,1,num-1) {
		a[++tot]=k[i];
		a[++tot]=LCA(k[i],k[i+1]);
	}
	a[++tot]=k[num];
	sort(a+1,a+1+tot,cmp);
	tot=unique(a+1,a+1+tot)-a-1;
	for_(i,1,tot-1) {
		int x=a[i],y=a[i+1];
		int L=LCA(x,y);
		e[L].pb(mkp(y,dis[y]-dis[L]));
	}
	flag=0;
	ll fS=DP(S);
	if(flag)cout<<fS<<"\n";
	else cout<<-1<<"\n";
}
inline ll read(){ll d=0,f=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch<='9'&&ch>='0'){d=(d<<1)+(d<<3)+ch-'0';ch=getchar();}return f?-d:d;}
int main(){
	n=rd,m=rd,S=rd,Q=rd;H=__lg(n)+1;
	for_(i,1,m){
		int x=rd,y=rd,val=rd;
		vv[x].pb(mkp(y,val));
		vv[y].pb(mkp(x,val));
	}
	dij();
	for_(i,1,n){
		int cur=i;
		while(cur){
			st[++tp]=cur;
			cur=id[cur];
		}
		for_(j,1,tp-1){
			int x=st[j],y=st[j+1];
			if(mp.find(P(min(x,y),max(x,y)))!=mp.end())break;
			mp[P(min(x,y),max(x,y))]=1;
			v[y].pb(mkp(x,dis[x]-dis[y]));
		}
		tp=0;
	}
	dep[S]=1;
	dfs_LCA(S);
	for_(j,1,H)for_(i,1,n)f[i][j]=f[f[i][j-1]][j-1];
	while(Q--){
		int op=rd;
		if(!op)For_(i,rd,1)in[rd]^=1;
		else{
			num=rd;
			for_(i,1,num)k[i]=rd;
			work();
		}
	}
	
	return 0;
}