比赛 10.10.18noip模拟 评测结果 WWWWTTWWWW
题目名称 罪犯问题C 最终得分 0
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-10-18 21:29:54
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;

const int MAXN=200005;
const int oo=100000000;

struct Node
{
	int v,w;
	Node *next;
	Node(int a,int b,Node*c):v(a),w(b),next(c){}
}*adj[MAXN];

queue<int> q;
int sta[MAXN];
int d[MAXN][2];
int N,M,K;

void spfa()
{
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(Node *p=adj[u];p;p=p->next)
		if (sta[p->v]==-1)
		{
			sta[p->v]=sta[u]^p->w;
			q.push(p->v);
		}
	}	
}

inline void add(int a,int b)
{
	adj[a]=new Node(abs(b),b>0,adj[a]);
	q.push(a);
	adj[abs(b)]=new Node(a,b>0,adj[abs(b)]);
	q.push(abs(b));
}

bool vis[MAXN];
void calcu(int i,int j)
{
	if (d[i][j]<oo)
		return ;
	vis[i]=true;
	bool flag=false;
	d[i][j]=0;
	for(Node *p=adj[i];p;p=p->next)
		if (!vis[p->v])
		{
			flag=true;
			calcu(p->v,j^p->w);
			calcu(p->v,!j^p->w);
			d[i][j]+=min(d[p->v][j^p->w],d[p->v][!j^p->w]+1);
		}
	if (!flag) d[i][j]=oo;
	vis[i]=false;
}

int main()
{
	freopen("criminalc.in","r",stdin);
	freopen("criminalc.out","w",stdout);
	scanf("%d%d%d",&N,&M,&K);
	memset(sta,-1,sizeof(sta));
	for(int i=0;i<M;i++)
	{
		int T;
		scanf("%d",&T);
		sta[T]=1;
		q.push(T);
	}
	for(int i=1;i<=N;i++)
	{
		int X;
		scanf("%d",&X);
		add(i,X);
	}
	spfa();
	for(int i=1;i<=N;i++)
	{
		d[i][0]=d[i][1]=oo;
		if(sta[i]!=-1)
		       	d[i][sta[i]]=0;
	}
	calcu(K,0);
	printf("%d\n",d[K][0]);
	return 0;
}