P2296 [NOIP2014 提高组] 寻找道路

• 分数
• • 估分
  • 实际分数
• 思路
• • 代码
  • 一点想法
• 正解
• • 错误原因
  • 正确思路
  • 正确代码

20 {color{Red}20} 20

20 {color{Red}20} 20

#include
using namespace std;
bool a[10010][10010];
int n,m;
int be,en;
bool find_[10010];
int finddp[10010];
bool find(int x){
	if(finddp[x]!=-1) return finddp[x];
	else if(x==en) return finddp[x]=1;
	else if(find_[x]!=0) return finddp[x]=0;
	else{
		bool u=0;
		find_[x]=1;
		for(int i=1;i<=n;i++){
			if(a[x][i]==1){
				u=u||find(i);
			}
		}
		find_[x]=0;
		return u;
	}
}
int findingdp[10010];
bool finding(int x){
	if(findingdp[x]!=-1){
		if(findingdp[x]==1) return 1;
		else return 0;
	}
	else{
		bool u=1;
		for(int i=1;i<=n;i++){
			if(a[x][i]==1){
				u=u&&find(i);
			}
		}
		return u;
	}
}
int fdp[10010];
bool f_[10010];
int f(int x){
	if(fdp[x]!=0) return fdp[x];
	else if(x==en) return 0;
	else if(finding(x)==0){
		return fdp[x]=-1;
		
	}
	else if(f_[x]==1) return fdp[x]=-1;
	else{
		int u=-1;
		f_[x]=1;
		for(int i=1;i<=n;i++){
			if(a[x][i]==1){
				int j=f(i);
				if(j!=-1){
					if(u==-1) u=j;
					else if(u!=-1&&u>j) u=j; 
				}  
			}
		}
		f_[x]=0;
		if(u!=-1) return fdp[x]=u+1;
		else return -1;
	}
}
int main(){
	memset(finddp,-1,sizeof(finddp));
	memset(findingdp,-1,sizeof(finddp));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		a[p][q]=1;
	}
	scanf("%d%d",&be,&en);
	printf("%dn",f(be));
	return 0;
}

find函数用于寻找一个点与终点是否相连
finding函数用于判断一个点是否符合路径上的点的要求
f函数用于寻找最短路
（可能的错误在于一个点是否通往终点的状态记录错误）

W r o n g   A n s w e r {color{Red}Wrongspace Answer} Wrong Answer

因为路径上的所有点的出边所指向的点都直接或间接与终点连通，所以我们不妨把所有的边反向，然后求t到s的最短路径

void travel(int k)
{
    h[k]=true;
    for(int i=p[k];i;i=next[k])
    if(!h[x[k]]) travel(x[k]);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x[i],&y[i]);
        next[i]=p[y[i]]; p[y[i]]=i;
    }
    scanf("%d %d",&s,&t);
    travel(t);
    memset(p,0,sizeof(p));
    for(int i=1;i<=m;i++) { next[i]=p[x[i]]; p[x[i]]=i; }
    memset(f,true,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=p[i];j;j=next[j])
            if(!h[y[j]]) f[i]=false;
    memset(d,127,sizeof(d));
    memset(h,false,sizeof(h));
    if(f[s]) d[s]=0;
    list[0]=s; h[s]=true;
    while(head<=tail)
    {
        for(int i=p[list[head]];i;i=next[i])
            if(f[y[i]] && d[x[i]]+1