传送门：【HDU】1317 XYZZY 题目分析：首先我们可以用spfa判最长路上是否有正权环，但是有正权环却不等价于能到达终点。这是我们还需要判断是否能从正权环中走到终点，这个可以用传递闭包搞定。如果没有正权环就看是否能从起点到终点就好了。 代码如下： #include <cstdio>#include <cstring>#include <algorithm>

http://acm.hdu.edu.cn/showproblem.php?pid=1317 大致题意：有n个房间，每个房间都有对应的能量值（可正可负），现在从1出发要到达n，初始能量为100，问是否能够达到n点，到达n的条件是中间及最后的能量值都要大于0. 思路：若不考虑环，那么求最长路判断是否大于0即可。若存在负环，对求最长路也没影响；但当存在正环时，最长路就不存在了。可用sp

题目：10557 - XYZZY 题目大意：就是一款游戏，冒险本来的能量是100，每进一间屋子就可以把屋子里的能量占为己有，但是屋子能量有正有负，然后给起点终点，看能否成功的到达终点。并且一间屋子可以重复进去多次。 解题思路：刚开始想用dfs， 但是题目里面会有环，会出现死循环，一直没想到思路。后来看了别人的代码。才发现可以巧妙的用dfs和bfs。 bfs（）是用来只寻找是否有到达终点

题意：给你n个房间 开始有能量值100 判断能否从1到第n个房间 每到一个房间可以获得能量x(可能小于0)  每到一个房间总能量必须大于0 每个房间可以重复到达 思路：求一个从1到n的最长路 不过可能有正环 没有正环 直接求最长路 如果有正环 判断环中的点是否可以到达n 具体用Bellman-Ford算法 虽然复杂度是(n*m)这题应该可以了 如果迭代n-1次之后还能松弛 说明有正环 然后