系统显示 Segmentation fault with invalid memory reference. 记录

一些尝试

1. 本蒟蒻感觉应该数组大小没有错……? 增大 N , M , MAXN的值，无果

2. #define int long long , 还是无果

3. 将priority_queue<pair<int,int>>改为priority_queue<pair<int,int> >, 依旧无果

4. orz 当然是求助大佬宁啦……（

P.S.

First orz&thx for 大佬宁

And RP++

Code

#include<bits/stdc++.h>
using namespace std;
const int N=60010,M=120010,MAXN=610;

int n,m,k,q;
int val[N];//标记 
bool flag;//记录是否找到被标记投放区域 
int r[MAXN],num;//r回收区域编号 
int h[N],to[M<<1],len[M<<1],nxt[M<<1],cnt;//链式前向星建图 

void addedge(int u,int v,int l)//建边 
{
	cnt++;
	nxt[cnt]=h[u];
	h[u]=cnt;
	to[cnt]=v;
	len[cnt]=l;
}

int pre[N],Len[N];//pre[i]记录节点i的前一个节点 Len[i]记录i和pre[i]的距离
int dis[N];//Dijkstra中当前最短距离 

void Find_Tree()//Dijkstra求以k为根的最小路径树 
{
	memset(dis,-1,sizeof(dis));
	priority_queue<pair<int,int>> q;
	q.push(make_pair(0,k));
	dis[k]=0;
	while(!q.empty())
	{
		int d=-q.top().first,u=q.top().second;
		q.pop();
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i];
			if(dis[v]==-1||dis[v]>dis[u]+len[i]) 
			{
				pre[v]=u;
				Len[v]=len[i];
				dis[v]=dis[u]+len[i];
				q.push(make_pair(-dis[v],v));
			}
			else if(dis[v]==dis[u]+len[i]&&pre[v]>u)
			{
				pre[v]=u;
				Len[v]=len[i];
			}
		}
	}
	memset(h,0,sizeof(h));
	cnt=0;
	for(int i=1;i<=n;i++)
		if(i!=k)
		{
			addedge(pre[i],i,Len[i]);
			addedge(i,pre[i],Len[i]);
		}
}

int dfn[N],DFN;//时间戳 
int dep[N],f[N][21];//dep[i]记录节点i在树上深度 f记录祖先 

void dfs(int u,int fa){//LCA预处理 
	dfn[u]=++DFN;//同时记录时间戳 
	dep[u]=dep[fa]+1;
	for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		f[v][0]=u;
		dfs(v,u);
	}
}

int lca(int x,int y){//求x和y的LCA 
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return y;
	}
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	return f[x][0];
}

//虚树实点+虚点数组要开两倍 
int vt[MAXN<<1],vtcnt;//vt存储虚树中的点 vtcnt虚树节点个数 
vector<int> VT[MAXN<<1];//VT vector存虚树 

bool cmp(int a,int b){ return dfn[a]<dfn[b]; }

void Virtual_Tree()//建虚树 
{
	vtcnt=0;
	sort(r+1,r+1+num,cmp); 
	for(int i=1;i<num;i++)
	{
		vt[++vtcnt]=r[i];
		vt[++vtcnt]=lca(r[i],r[i+1]);
	}
	vt[++vtcnt]=r[num];
	sort(vt+1,vt+1+vtcnt,cmp);
	vtcnt=unique(vt+1,vt+1+vtcnt)-vt-1;
	for(int i=1;i<vtcnt;i++)
	{
		int l=lca(vt[i],vt[i+1]);
		VT[l].push_back(vt[i+1]);
	}
}

int calc(int u)//求最小代价 
{
	int res=0;
	if(val[u]) flag=1;
	int siz=VT[u].size();
	for(int i=0;i<siz;i++)
	{
		int v=VT[u][i];
		int tmp=min(dis[v]-dis[u],calc(v));
		if(val[v]) res+=dis[v]-dis[u];
		else res+=tmp;
	}
	VT[u].clear();
	return res;
}

int main()
{
	cin>>n>>m>>k>>q;
	for(int i=1;i<=m;i++)
	{
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		addedge(u,v,l);
		addedge(v,u,l);
	}
	Find_Tree();
	dfs(k,0);
	while(q--)
	{
		int opt;
		scanf("%d%d",&opt,&num);
		if(!opt)//opt==0 区域标记取反 
		{
			for(int i=1;i<=num;i++)
			{
				int p;
				scanf("%d",&p);
				val[p]^=1;
			}
		}
		else//opt==1 建虚树 + DP
		{
			for(int i=1;i<=num;i++) scanf("%d",&r[i]);
			r[++num]=k;
			Virtual_Tree();
			flag=0;
			int ans=calc(k);
			if(flag) printf("%d\n",ans);
			else printf("-1\n");
		}
	}
	return 0;
}