说说：

这道题相对来说，感觉难度稍大一点，因为有好几个点到后来才想到。首先题目给你一系列的节点，序号从1到n，并且告诉你每个节点可以进入的下一个节点的序号。假设开始你有能量值100，现在要求你从节点1开始，不断地从一个节点进入另一个节点，当然进入的时候你的能量值要加上节点代表的数值（范围是-100到+100）。并且你可以重复进入同一个节点多次。当你的能力值小于等于0时，你就失败了。问你有没有办法能从节点1走到节点n。下面来说一说解题方法：首先最令人感到痛苦的是，一个节点可以重复经过，这样的话，如果不断DFS很可能死循环出不来了。所以我就设了一个数组，标记第一次进入某个节点时，此时的能量值。但是后来仔细一想，其实不一定要走到最后一个节点n，只要能够重复到达一个节点，并且之后的能量值比后来要大，那么必然是能成功到达最终节点的。不过这个想法其实是错误的，因为这是一个单向图，很有可能在一个圈子里绕，然后就出不来了。所以有必要判断一下每个节点在不管能量值的情况下，能否到达最终节点。在这次的题解报告中，我其实用的方法比较笨啦，就是把每个节点DFS一遍，其实只要从最终节点逆DFS一下，碰到个节点做一下标记也是OK的。根据以上的分析，我们就可以从节点1开始DFS了，其中当再次到达一个节点，并且当到达一个到不了最终节点的节点或者再次到达一个节点，且此次的能量值小于等于第一次到的能量值，则停此节点停止DFS。最后当再次到达一个节点，且能量值大于第一次，该节点也可以到达最终节点，那么整个遍历都是成功的。（省略了明显的成功或失败的情况）详细的解题步骤，请阅读下面的源代码。

源代码：

#include <stdio.h>
#include <string.h>
#define MAXN 100+5

int room[MAXN];//每个节点的能量值
int roomconnect[MAXN][MAXN];//该节点可以到达的节点且第一个元素为可到达的节点个数
int roomenergy[MAXN];//第一次到达某节点的能量值
int roomvisit[MAXN];//dfs标记
char abletofinish[MAXN];//该节点能否到达最终节点
int energy;
int n;

int edfs(int);//考虑能量值
int dfs(int);//判断某节点能否到最终节点，不考虑能量值

int main(){
  int i,j;
//  freopen("data","r",stdin);
  while(scanf("%d",&n)&&n!=-1){
    energy=100;
    for(i=1;i<=n;i++){
      scanf("%d",&room[i]);
      scanf("%d",&roomconnect[i][0]);
      for(j=1;j<=roomconnect[i][0];j++)
        scanf("%d",&roomconnect[i][j]);
    }

    for(i=1;i<=n;i++){
      roomenergy[i]=-1;
      memset(roomvisit,0,sizeof(roomvisit));
      abletofinish[i]=dfs(i);//判断每个节点能否到达最终节点，不考虑能量值
    }

    if(edfs(1))
      printf("winnable\n");
    else
      printf("hopeless\n");
    
  }

  return 0;
}

int edfs(int num){
  int i;

  energy+=room[num];
  
  if(!abletofinish[num]){//该节点不能到达最终节点
    energy-=room[num];//注意回溯
    return 0;
  }
  else if(energy<=roomenergy[num]||energy<=0){//再次到达某节点，且能量值小于等于第一次的值，则不再深搜
    energy-=room[num];
    return 0;
  }
  else if(num==n&&energy>0||roomenergy[num]!=-1&&energy>roomenergy[num]){//再次到达某节点，且能量值大于第一次，且该节点能到最终节点，则成功
    energy-=room[num];
    return 1;
  }
  roomenergy[num]=energy;
  
  for(i=1;i<=roomconnect[num][0];i++)
    if(edfs(roomconnect[num][i])){
      energy-=room[num];
      return 1;
    }

  return 0;
}

int dfs(int num){
  int i;
  if(num==n)
    return 1;
  roomvisit[num]=1;
  for(i=1;i<=roomconnect[num][0];i++)
    if(!roomvisit[roomconnect[num][i]])
       if(dfs(roomconnect[num][i]))
          return 1;
         
  return 0;
}

XYZZY UVA 10557 （接近于有向图的最长路问题）