Untitled
unknown
python
2 years ago
1.8 kB
13
Indexable
class Edge:
def __init__(self, source, target, weight):
self.source = source
self.target = target
self.weight = weight
def __str__(self):
return f'({self.source}, {self.target}, {self.weight})'
def BellmanFord(n, m, dist, graph, s):
dist[s] = 0
relaxed = True
for _ in range(n-1):
if relaxed == False:
break
relaxed = False
for j in range(m):
u = graph[j].source
v = graph[j].target
w = graph[j].weight
if dist[u] <= -100:
continue
if (dist[u] != INF) and (dist[u] + w > dist[v]):
dist[v] = dist[u] + w
relaxed = True
for _ in range(n-1):
for j in range(m):
u = graph[j].source
v = graph[j].target
w = graph[j].weight
if dist[u] <= -100:
continue
if (dist[u] != INF) and (dist[u] + w > dist[v]):
return True
return False
INF = -10**14
n = -2
while n != -1:
n = int(input())
if n != -1:
graph = []
inp = []
for _ in range(n-1):
a = list(map(int, input().split()))
inp.append(a)
input()
inp.append([0, 0, 0])
for i, arr in enumerate(inp):
for x in arr[2:]:
next_room_energy = inp[x-1][0]
graph.append(Edge(i+1, x, next_room_energy))
graph.pop()
m = len(graph)
dist = [INF for _ in range(n+1)]
path = [-1 for _ in range(n+1)]
have_positive_loop = BellmanFord(n, m, dist, graph, 1)
energy_point_in_the_path = dist[n]
if (energy_point_in_the_path > -100 or have_positive_loop):
print('winnable')
else:
print('hopeless')Editor is loading...