rt

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
map<int,map<int,int>> mp;
int n,m,k,Q,num,len,dp[N],dis[N],dl[N],vis[N],vv[N],a[N],b[N],dfn[N],tot,dep[N],fa[N][20];
vector<int> ee[N],ww[N],e[N],w[N],ve[N],vw[N];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
struct node{
	int lst,dis,x;
	bool operator<(const node b)const{
		if(dis!=b.dis) return dis>b.dis;
		else return lst>b.lst;
	}
};
priority_queue<node> q;
void dij(){
	dis[k]=0;
	q.push({0,0,k});
	while(!q.empty()){
		node tmp=q.top();q.pop();
		int x=tmp.x;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=0;i<ee[x].size();i++){
			int y=ee[x][i],W=ww[x][i];
			if(dis[y]>dis[x]+W){
				if(mp[x][y]==0){
					mp[x][y]=mp[y][x]=1;
					e[y].push_back(x);
					e[x].push_back(y);
					w[x].push_back(W);
					w[y].push_back(W);
				}
				dis[y]=dis[x]+W;
				q.push({x,dis[x]+W,y});
			}
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--){
		if((dep[x]-dep[y])>=(1<<i)){
			x=fa[x][i];
		}
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}
void dfs(int x,int f,int dp,int siz){
	dep[x]=dp,fa[x][0]=f,dfn[x]=++tot,dl[x]=siz;
	for(int i=0;i<e[x].size();i++){
		int y=e[x][i];
		if(y==f) continue;
		dfs(y,x,dp+1,siz+w[x][i]);
	}
}
inline int Dis(int x,int y){
	int lc=lca(x,y);
	return dl[x]+dl[y]-2*dl[lc];
}
int tt;
void work_change(){
	num=read();
	for(int i=1;i<=num;i++){
		int xx=read();
		if(vis[xx]==1) tt--;
		else tt++;
		vis[xx]=1-vis[xx];
	}
}
bool cmp_dfn(int x,int y){
	return dfn[x]<dfn[y];
}
void add_edge(int x,int y){
	ve[x].push_back(y);
	ve[y].push_back(x);
	int ds=Dis(x,y);
	vw[x].push_back(ds);
	vw[y].push_back(ds);
}
void build_virtual_tree(){
	tot=0;
	sort(a+1,a+num+1,cmp_dfn);
	for(int i=1;i<num;i++){
		b[++tot]=a[i];
		b[++tot]=lca(a[i],a[i+1]);
		vv[a[i]]=1;
	}
	vv[a[num]]=1;
	b[++tot]=a[num];
	sort(b+1,b+tot+1,cmp_dfn);
	len=unique(b+1,b+tot+1)-b-1;
	for(int i=1;i<len;i++){
		add_edge(b[i+1],lca(b[i],b[i+1]));
	}
}
void clear(int x){
	ve[x].clear();
	vw[x].clear();
}
void clear_virtual_tree(){
	for(int i=1;i<len;i++){
		clear(b[i+1]),clear(lca(b[i],b[i+1]));
	}
	for(int i=1;i<=k;i++){
		vv[a[i]]=0;
	}
}
void dfs_dp(int x,int f){
	dp[x]=0;
	for(int i=0;i<ve[x].size();i++){
		int y=ve[x][i];
		if(y==f) continue;
		dfs_dp(y,x);
		if(vis[y]==1) dp[x]+=vw[x][i];
		else dp[x]+=min(vw[x][i],dp[y]);
	}
}
void work_output(){
	num=read();
	for(int i=1;i<=num;i++){
		a[i]=read();
	}
	num++,a[num]=k;
	build_virtual_tree();
	dfs_dp(k,0);
	if(dp[k]==0) dp[k]=-1; 
	cout<<dp[k]<<endl;
/*	for(int i=1;i<=n;i++){
		cout<<vis[i]<<" ";
	}
	cout<<endl;
	for(int i=1;i<=n;i++){
		cout<<dp[i]<<" ";
	}
	cout<<endl;*/
	clear_virtual_tree();
}
void init_fa(){
	for(int i=1;i<=19;i++){
		for(int j=1;j<=n;j++){
			fa[j][i]=fa[fa[j][i-1]][i-1];
		}
	}
}
signed main(){
//	freopen("P5680_7.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read(),m=read(),k=read(),Q=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),len=read();
		ee[u].push_back(v);
		ee[v].push_back(u);
		ww[u].push_back(len);
		ww[v].push_back(len);
	}
	for(int i=1;i<=n;i++) dis[i]=2e9;
	dij();
/*	for(int i=1;i<=n;i++){
		cout<<"i "<<i<<" "<<dis[i]<<endl;
	}*/
	memset(vis,0,sizeof(vis));
	dfs(k,0,1,0);
	init_fa();
/*	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			cout<<"i j lca "<<i<<" "<<j<<" "<<lca(i,j)<<endl;
		}
	}*/
	while(Q--){
		int op=read();
		if(op==0) work_change();
		else work_output();
	}
	return 0;
}

不知道为啥 MLE on 9,10