題目如下：
ADVENT: /ad?vent/, n.The prototypical computer adventure game, first designed by Will Crowther on the PDP-10 in the mid-1970s as an attempt at computer-refereed fantasy gaming, and expanded into a puzzle-oriented game by Don Woods at Stanford in 1976. (Woods had been one of the authors of INTERCAL.) Now better known as Adventure or Colossal Cave Adventure, but the TOPS-10 operating system permitted only six-letter filenames in uppercase. See also vadding, Zork, and Infocom.
It has recently been discovered how to run open-source software on theY-Crate gaming device. A number of enterprising designers have developedAdvent-style games for deployment on the Y-Crate. Your jobis to test a number of these designs to see which are winnable.
Each game consists of a set of up to 100 rooms. One of therooms is the start and one of the rooms is the finish.Each room has an energy value between -100 and +100.One-way doorways interconnect pairs of rooms.
The player begins in the start room with 100 energy points. She maypass through any doorway that connects the room she is in to another room, thusentering the other room. The energy value of this room is added tothe player's energy. This process continues until she wins by enteringthe finish room or dies by running out of energy (or quits in frustration). During her adventurethe player may enter the same room several times, receiving its energyeach time.
The input consists of several test cases. Each test case begins withn, the number of rooms. The rooms are numbered from 1 (the start room) to n (the finish room). Input for the n rooms follows. The input for each room consists of one or more lines containing:
the energy value for room i the number of doorways leaving room ia list of the rooms that are reachable by the doorways leaving room i The start and finish rooms will always have enery level 0. A line containing-1 follows the last test case.In one line for each case, output "winnable" if it is possible forthe player to win, otherwise output "hopeless".
5 0 1 2 -60 1 3 -60 1 4 20 1 5 0 0 5 0 1 2 20 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 21 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 20 2 1 3 -60 1 4 -60 1 5 0 0 -1
hopeless hopeless winnable winnable
問一個點到另一個點是否可達，每個點有權值（能量），要求能量和始終大於0，並且可能有圈。在無圈的情況下用SPFA算法可以求得最長路徑，只要最長路徑大於0就可以判斷為成功。在有圈情況下，SPFA可以判斷出圈（節點總數大於N即說明有圈），如果產生的是正圈（負圈直接無視，因為不會傻到走負圈讓能量減少），並且產生正圈的點在不考慮能量的情況下可以到達終點（直接DFS即可），則可以判斷為成功。否則失敗。因為其余情況要麼是點根本就不能到達終點，要麼是能量不滿足。
AC的代碼如下；
