Scribd Logo
Upload

Welcome to Scribd!

  • 1 views

    Flight optimization

    Uploaded by

    Sanjai Raj

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd

    Flight optimization

    Uploaded by

    Sanjai Raj
    1 views2 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    TXT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    1 views2 pages

    Flight optimization

    Uploaded by

    Sanjai Raj

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    of 2

    Flight optimization

    import heapq
    from datetime import datetime

    class Flight:
    def __init__(self, source, destination, departure, arrival, price):
    self.source = source
    self.destination = destination
    self.departure = parse_time(departure)
    self.arrival = parse_time(arrival)
    self.price = price

    def parse_time(time_str):
    hour = int(time_str[:2])
    minute = int(time_str[3:5])
    meridian = time_str[5:].strip()

    if meridian == "Am" and hour == 12:


    hour = 0
    elif meridian == "Pm" and hour != 12:
    hour += 12

    return hour * 60 + minute

    def find_cheapest_flight():
    num_flights = int(input())
    flights = []
    flight_map = {}

    for _ in range(num_flights):
    source, dest, departure, arrival, price = input().split()
    price = int(price)
    flight = Flight(source, dest, departure, arrival, price)
    flights.append(flight)
    if source not in flight_map:
    flight_map[source] = []
    flight_map[source].append(flight)

    start, end = input().split()


    earliest_departure, latest_arrival = input().split()
    earliest_departure = parse_time(earliest_departure)
    latest_arrival = parse_time(latest_arrival)

    queue = []
    for flight in flight_map.get(start, []):
    if flight.departure >= earliest_departure and flight.arrival <=
    latest_arrival:
    heapq.heappush(queue, (flight.price, flight.arrival,
    flight.destination))

    min_cost = {}
    arrival_time = {}

    while queue:
    cost, current_arrival, city = heapq.heappop(queue)

    if city in min_cost and (cost > min_cost[city] or (cost == min_cost[city]


    and current_arrival >= arrival_time[city])):
    continue
    min_cost[city] = cost
    arrival_time[city] = current_arrival

    if city == end:
    print(cost)
    return

    for flight in flight_map.get(city, []):


    if flight.departure >= current_arrival and flight.departure >=
    earliest_departure and flight.arrival <= latest_arrival:
    heapq.heappush(queue, (cost + flight.price, flight.arrival,
    flight.destination))

    print("Impossible")

    if __name__ == "__main__":
    find_cheapest_flight()

    You might also like