Вычислить кратчайший путь в графе с взвешенными вершинами

Question

В настоящее время я работаю над проблемой kattis: Treasure Hunt, Link. Цель состоит в том, чтобы найти путь, который будет стоить меньше всего дней, чтобы добраться до сокровища.

В настоящее время я использую алгоритм Дейкстры с взвешенными вершинами для вычисления кратчайшего пути к сокровищу. Я определил класс "Узел", в котором я определяю его вес и предыдущий узел, если он назначен. Я использую heapq, и мне нужно переопределить метод lt в моем классе Node.

Когда кратчайший маршрут определен, я пытаюсь подсчитать количество дней, которые потребуются для прохождения этого кратчайшего маршрута.

Я знаю, что это не кодекс штрафов, извините.

Определение соседних узлов и поиск пути

   def createNode(row):
        rl = list()
        for x in row:
            rl.append(Node(x))
        return rl

    rows, columns, stamina = map(int, input().split(' '))
    treasure_map = list()
    for row in range(rows):
        treasure_map.append(list(input()))
    treasure_map = list(map(createNode, treasure_map))
    for x in range(len(treasure_map)):
        for y in range(len(treasure_map[x])):
            tile = treasure_map[x][y]
            # add tile to south link
            if x - 1 >= 0 and treasure_map[x - 1][y] is not None:
                tile.add_neighbour(treasure_map[x - 1][y])
            if y + 1 < len(treasure_map[x]) and treasure_map[x][y + 1] is not None:
                tile.add_neighbour(treasure_map[x][y + 1])
            if x+1 < len(treasure_map) and treasure_map[x + 1][y] is not None:
                tile.add_neighbour(treasure_map[x + 1][y])
            if y - 1 >= 0 and treasure_map[x][y - 1] is not None:
                tile.add_neighbour(treasure_map[x][y - 1])

    visited = list()
    nodes = list()
    for x in treasure_map:
        for y in x:
            if y.name is not '#':
                nodes.append(y)
    heapq.heapify(nodes)
    endpoint = None

    if len(nodes) < 2:
        print(-1)

    # Search route with minimum load
    while nodes:
        curr = heapq.heappop(nodes)
        if curr.name is 'G':
            endpoint = curr
            break
        for node in curr.get_neighbours():
            if node not in visited and not node.load > stamina:
                if curr.weight + curr.load < node.weight:
                    node.add_previous(curr)
        visited.append(curr)
        heapq.heapify(nodes)

Код расчета дней, необходимых для прохождения от начала до конца: (еще раз знаю, что может быть лучше)

   if endpoint is not None:
        nexNode = endpoint.previous
        found = False
        stamina_to_use = list()
        while nexNode:
            if nexNode.name == "S":
                # Maybe count the day here
                found = True
            stamina_to_use.append(nexNode.load)
            nexNode = nexNode.previous
        days = 1
        curr = stamina
        counter = 0
        stamina_to_use.reverse()
        # Count the number of days needed for finishing
        while stamina_to_use:
            tocheck = stamina_to_use.pop()
            # print("Current days: {}, current stamina: {},stamina to withdraw {}".format(
            #    days, curr, tocheck))
            if curr > stamina:
                print(-1)
                break
            if (curr - tocheck) < 0:
                days += 1
                curr = stamina
            curr -= tocheck
        if found:
            print(days)
        else:
            print(-1)

    else:
        print(-1)

Результаты на самом деле такие, как я ожидал, я получаю кратчайший путь и получаю нужное количество дней в соответствии с моими собственными тестами, а также с тестами на kattis. Но по какой-то причине, когда я отправляю проект в kattis, первые 8 тестовых примеров проходят, а затем я внезапно получаю: "Неверный ответ", я не знаю, где ошибка в моем мышлении или коде. Правильно ли мой подход, или я должен использовать другой? Или в подсчете дней допущена простая ошибка?

заранее спасибо

Answer 1

Вот решение, которое почти работает, отсутствует небольшая проверка.

Таким образом, вам нужно выяснить, что он делает:)

BIG_NUMBER = 9999
STAMINA_COST = {'F': 2, 'M': 3}

def maybe_update(field1, field2, maze, time_taken, n, m, k, updated_fields):
    i1, j1 = field1
    i2, j2 = field2
    if not (0 <= i2 < n and 0 <= j2 < m):
        # Out of bounds
        return
    field = maze[i2][j2]
    if field == '#':
        # Can not walk on river
        return
    days_taken, stamina_taken = time_taken[i1][j1]
    stamina_to_move = STAMINA_COST.get(field, 1)
    stamina_taken += stamina_to_move
    if k < stamina_taken:
        days_taken += 1
        stamina_taken = stamina_to_move
    new_time_taken = (days_taken, stamina_taken)
    if new_time_taken < time_taken[i2][j2]:
        time_taken[i2][j2] = new_time_taken
        updated_fields.add((i2, j2))

def main():
    # Read input
    n, m, k = map(int, input().split())
    maze = []
    for i in range(n):
        line = input()
        maze.append(line)

    # Create map of how long it takes to get somewhere
    # Each field has (days_spent, stamina_spent)
    time_taken = []
    for i in range(n):
        time_taken.append([(BIG_NUMBER, BIG_NUMBER) for j in range(m)])

    # Look for the start and mark it as (1, 0), also look for the gold
    updated_fields = set()
    for i in range(n):
        for j in range(m):
            if maze[i][j] == 'S':
                time_taken[i][j] = (1, 0)
                updated_fields.add((i, j))
            elif maze[i][j] == 'G':
                gold_at = (i, j)

    # BFS to propagate time_taken
    while updated_fields:
        i, j = updated_fields.pop()
        maybe_update((i, j), (i + 1, j), maze, time_taken, n, m, k, updated_fields)
        maybe_update((i, j), (i - 1, j), maze, time_taken, n, m, k, updated_fields)
        maybe_update((i, j), (i, j + 1), maze, time_taken, n, m, k, updated_fields)
        maybe_update((i, j), (i, j - 1), maze, time_taken, n, m, k, updated_fields)

    # Print days taken to get to the gold
    i, j = gold_at
    days_taken = time_taken[i][j][0]
    print(-1 if days_taken == BIG_NUMBER else days_taken)

if __name__ == '__main__':
    main()