#include<stdio.h>
#include<string.h>

int room[120][120];
int n,energy[120];

int bfs(int index)
{
	if(index==n)
		return 1;
	char vis[120],s[120];
	memset(vis,0,120);
	int front=0,rear=1,i,j;
	vis[index]=1;
	s[front]=index;
	while(front<rear)
	{
		for(i=1;i<=room[s[front]][119];i++)
		{
			if(room[s[front]][i]==n)
				return 1;
			if(!vis[room[s[front]][i]])
			{
				s[rear++]=room[s[front]][i];
				vis[room[s[front]][i]]=1;
			}
		}
		front++;
	}
	return 0;
}

int dfs(int child,int score)
{
	if(score+room[child][0]<=0||bfs(child)==0)
		return 0;
	if(child==n)
		return 1;
	int i,j;
	energy[child]=score+room[child][0];
	for(i=1;i<=room[child][119];i++)
	{
		if(energy[room[child][i]]==0)
		{
				if(dfs(room[child][i],score+room[child][0]))
				{
					//energy[room[child][i]]=0;//不加这两句就AC加上就会 tle
					return 1;
				}
				//else
					//energy[room[child][i]]=0;
		}
		else if(energy[room[child][i]]!=0)
		{
			if(score+room[child][0]+room[room[child][i]][0]>energy[room[child][i]])
			{
				return 1;
			}
			else
				continue;
		}
	}
		return 0;
}

int main()
{
	int i,j;
	while(scanf("%d",&n)&&n!=-1)
	{
		for(i=1;i<=n;i++)
		{
			scanf("%d",&room[i][0]);
			scanf("%d",&room[i][119]);
			for(j=1;j<=room[i][119];j++)
			{
				scanf("%d",&room[i][j]);
			}
		}
		memset(energy,0,480);
		if(dfs(1,100)==0)
			printf("hopeless\n");
		else
			printf("winnable\n");
	}
	return 0;
}




问题在写了注释的地方，如果递归调用结束了，就把energy标记清空，使得别的经过此点的路径能沿伸下去。我这样做的意义在于，如果第一条经过此点的路径在中途能量小于0，就返回，但由于别的经过这点的路径可能到达终点，所以要把标记清空，使得别的路径能延伸下去。可是，我提交了n次都tle，去掉这两句后却ac了。
瞬间迷茫了，难道我自己对于图的遍历理解错了？可我怎么也想不明白错在哪。或者是测试数据不够强，没有我说的那种情况？

• Re:求助，是这道题有问题还是我自己逻辑推理错了 (169) cgjiayou 2014-08-11 21:33:51