问题2105--游戏玩家

2105: 游戏玩家

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

有n （n ≤100）个房间，每个房间都有一个能量值（范围是-100～+100）。以单向门连接两个房间，可以通过任何连接所在房间的门到达另一个房间，从而进入另一个房间，到达该房间时会自动获得该房间的能量。可以多次进入同一个房间，每次都能获得能量。初始能量值为100，初始位置是1号房间，要走到n号房间。1号房间和n 号房间的能量值均为0。到达n 号房间可获胜，如果中途能量值小于或等于0，则会因能量耗尽而死亡。

输入

输入包含几个测试用例。每个测试用例的第1行都为n ，表示房间数。接下来是n 个房间的信息。每个房间的信息都包括：房间i 的能量值、离开房间i 的门数量、房间i 可以通过门到达的房间列表。在最后一个测试用例之后是包含-1的行。

输出

如果玩家有可能获胜， 则输出winnable ， 否则输出hopeless。

样例输入 Copy 

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

样例输出 Copy 

hopeless
hopeless
winnable
winnable

来源/分类

关键路径 Floyd算法 SPFA算法 
[提交] [状态]