Нашли ошибку?

Купон на один рейс

СложнаяДописатьГлава 7
Нашли ошибку?

#алгоритм Дейкстры#состояния#очередь с приоритетомid: ga-coupon-flight

У путешественника есть один купон: на любом одном рейсе он платит половину цены (с округлением вниз — price // 2). Допишите cheapest_with_coupon(flights, start, goal): функция возвращает минимальную цену перелёта или None. Купон можно и не использовать. Пропуски помечены # TODO.

Пример

flights = {
    "A": {"B": 1000, "C": 300},
    "C": {"B": 600},
}
cheapest_with_coupon(flights, "A", "B")   # 500: прямой рейс за 1000 // 2
# без купона было бы 900 через C, с купоном на C → B — 600

Решение

import heapq
import math


def cheapest_with_coupon(flights: dict[str, dict[str, int]], start: str, goal: str) -> int | None:
    """Минимальная цена с одним купоном на полцены или None."""
    best: dict[tuple[str, bool], int] = {(start, False): 0}
    done: set[tuple[str, bool]] = set()
    heap = [(0, start, False)]  # (цена, город, купон уже использован?)

    def relax(city: str, used: bool, cost: int) -> None:
        if cost < best.get((city, used), math.inf):
            best[(city, used)] = cost
            heapq.heappush(heap, (cost, city, used))

    while heap:
        cost, city, used = heapq.heappop(heap)
        if (city, used) in done:
            continue
        if city == goal:
            return cost
        done.add((city, used))
        for nxt, price in flights.get(city, {}).items():
            # TODO: лететь по полной цене — купон не тратится
            # TODO: если купон ещё есть — лететь за price // 2 и перейти в состояние «купон использован»
            pass
    return None

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 coupon_flight.py — тесты те же, результат покажет ✓ / ✗ и итог.