前置知识
解法
题目中所说的 回收路线树 即以 \(k\) 为根节点的最短路径树，可以使用 Dijkstra 构建。
标记 回收区域 本质上是对 回收区域 构建虚树，然后就和 luogu P2495 [SDOI2011] 消耗战 基本一致了，根据儿子节点的 投放 状态进行树形 DP 转移。
注意本题中虚树上两点边权为原最短路径树上两点间的距离。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct node
{
int nxt,to,w;
}e[200010];
int head[50010],dis[50010],vis[50010],fa[50010],siz[50010],son[50010],dep[50010],top[50010],dfn[50010],a[50010],f[50010],tot=0,cnt=0;
pair<int,int>pre[50010];
void add(int u,int v,int w)
{
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
void dijkstra(int k)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
priority_queue<pair<int,int> >q;
q.push(make_pair(0,k));
dis[k]=0;
while(q.empty()==0)
{
int x=q.top().second;
q.pop();
if(vis[x]==0)
{
vis[x]=1;
for(int i=head[x];i!=0;i=e[i].nxt)
{
if(dis[e[i].to]==0x3f3f3f3f||dis[e[i].to]>dis[x]+e[i].w)
{
dis[e[i].to]=dis[x]+e[i].w;
pre[e[i].to]=make_pair(x,e[i].w);
q.push(make_pair(-dis[e[i].to],e[i].to));
}
else
{
if(dis[e[i].to]==dis[x]+e[i].w&&pre[e[i].to].first>x)
{
pre[e[i].to]=make_pair(x,e[i].w);
}
}
}
}
}
}
void dfs1(int x,int father)
{
tot++;
dfn[x]=tot;
siz[x]=1;
fa[x]=father;
dep[x]=dep[father]+1;
for(int i=head[x];i!=0;i=e[i].nxt)
{
dis[e[i].to]=dis[x]+e[i].w;
dfs1(e[i].to,x);
siz[x]+=siz[e[i].to];
son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
}
}
void dfs2(int x,int id)
{
top[x]=id;
if(son[x]!=0)
{
dfs2(son[x],id);
for(int i=head[x];i!=0;i=e[i].nxt)
{
if(e[i].to!=son[x])
{
dfs2(e[i].to,e[i].to);
}
}
}
}
int lca(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]>dep[top[v]])
{
u=fa[top[u]];
}
else
{
v=fa[top[v]];
}
}
return dep[u]<dep[v]?u:v;
}
int get_dis(int x,int rt)
{
return dis[x]-dis[rt];
}
bool cmp(int a,int b)
{
return dfn[a]<dfn[b];
}
struct Vitrual_Tree
{
vector<int>g[50010];
stack<int>s;
void build(int len,int k)
{
sort(a+1,a+1+len,cmp);
while(s.empty()==0)
{
s.pop();
}
s.push(k);
g[k].clear();
for(int i=1;i<=len;i++)
{
int rt=lca(a[i],s.top());
while(s.top()!=rt)
{
int tmp=s.top();
s.pop();
if(dfn[s.top()]<dfn[rt])
{
s.push(rt);
g[rt].clear();
}
g[s.top()].push_back(tmp);
}
s.push(a[i]);
g[a[i]].clear();
}
while(s.top()!=k)
{
int tmp=s.top();
s.pop();
g[s.top()].push_back(tmp);
}
}
void dfs(int x)
{
f[x]=0;
for(int i=0;i<g[x].size();i++)
{
dfs(g[x][i]);
f[x]+=(vis[g[x][i]]==1)?get_dis(g[x][i],x):min(get_dis(g[x][i],x),f[g[x][i]]);
}
}
}V;
int main()
{
// #define Isaac
#ifdef Isaac
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
int n,m,q,k,u,v,w,i,j;
cin>>n>>m>>k>>q;
for(i=1;i<=m;i++)
{
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
dijkstra(k);
cnt=0;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
for(i=1;i<=n;i++)
{
if(i!=k)
{
add(pre[i].first,i,pre[i].second);
}
}
dfs1(k,0);
dfs2(k,k);
memset(vis,0,sizeof(vis));
for(j=1;j<=q;j++)
{
cin>>u>>m;
if(u==0)
{
for(i=1;i<=m;i++)
{
cin>>a[i];
vis[a[i]]^=1;
}
}
else
{
for(i=1;i<=m;i++)
{
cin>>a[i];
}
V.build(m,k);
V.dfs(k);
cout<<((f[k]==0)?-1:f[k])<<endl;
}
}
return 0;
}