比赛 |
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;
}