Untitled

 avatar
unknown
python
2 years ago
1.8 kB
6
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...