5

Задача:

Ограничение по времени: 1 сек.

Ограничение по памяти: 16Мб.

Между некоторыми деревнями края Власюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.

Марии Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).

Входные данные

Во входном файле INPUT.TXT записано число N - общее число деревень (1 ≤ N ≤ 100), номера деревень d и v, затем количество автобусных рейсов R (0 ≤ R ≤ 10000). Затем идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена - целые от 0 до 10000). Если в момент t пассажир приезжает в деревню, то уехать из нее он может в любой момент времени, начиная с t.

Выходные данные

В выходной файл OUTPUT.TXT вывести минимальное время, когда Мария Ивановна может оказаться в деревне v. Если она не сможет с помощью указанных автобусных рейсов добраться из d в v, вывести -1.

Пример:

Вход

3               
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10

Выход

5

Мой код:

from collections import deque  # импорт очереди для полследующего использования в алгоритме Дейкстры

# вход данных, где: N - общее число деревень, S и F - начальная и конечная деревня, R - количество рейсов.
N = int(input())
S, F = map(int, input().split())
R = int(input())

# если мы входим в ту же деревню, то время 0
if S == F and N >= S and N >= F:
    print(0)
    exit()

# сразу проверяем: если рейсов не будет
if R == 0:
    # мы уже проверили на вхождение в одну и ту же деревню
    print(-1)
    exit()

# функция для создания графа
def filling_in_the_graph(tables: list[tuple] = None) -> dict:
    g = dict()  # создаём словарь
    # Если вы не вписали tables:
    if not tables:
        for i in range(R):  # ждём на вход R - рейсов
            table = tuple(map(int, input().split()))  # получаем на вход рейс

            # распределяем на вход значения по переменным
            leave = table[0]  # table[0] - из какой деревни мы выезжаем
            move_in = table[2]  # table[2] - в какую деревню мы приезжаем
            time_leave = table[1]  # table[1] - в какое время мы выезжаем
            time_move_in = table[3] # table[3] - в какое время мы приезжаем

            # Если этого рейса(вершины) нет, создаём его
            if leave not in g:
                g[leave] = {move_in: [time_leave, time_move_in]}

            # Иначе если, мы выезжаем из одной деревни, но у нас пути из этой деревни(вершины), создаём его
            elif move_in not in g[leave]:
                g[leave][move_in] = [time_leave, time_move_in]

            # Иначе если, у нас уже есть этот путь, тогда выбираем самый короткий по времени
            elif sum(g[leave][move_in]) > time_leave + time_move_in:
                g[leave][move_in] = [time_leave, time_move_in]

    # Вписали
    else:
        for table in tables:  # обходим каждый рейс
            # распределяем на вход значения по переменным
            leave = table[0]  # table[0] - из какой деревни мы выезжаем
            move_in = table[2]  # table[2] - в какую деревню мы приезжаем
            time_leave = table[1]  # table[1] - в какое время мы выезжаем
            time_move_in = table[3]  # table[3] - в какое время мы приезжаем

            # Если этого рейса(вершины) нет, создаём его
            if leave not in g:
                g[leave] = {move_in: [time_leave, time_move_in]}

            # Иначе если, мы выезжаем из одной деревни, но у нас пути из этой деревни(вершины), создаём его
            elif move_in not in g[leave]:
                g[leave][move_in] = [time_leave, time_move_in]

            # Иначе если, у нас уже есть этот путь, тогда выбираем самый короткий по времени
            elif sum(g[leave][move_in]) > time_leave + time_move_in:
                g[leave][move_in] = [time_leave, time_move_in]


    # вписываем те деревни, из которых никуда не попасть
    for i in range(1, R + 1):
        if i not in g:
            g[i] = dict()

    return g  # возвращаем наш граф


# graph = filling_in_the_graph([(1, 0, 2, 5), (1, 1, 2, 3), (2, 3, 3, 5), (1, 1, 3, 10)]) - для тех, кто вписывает
graph = filling_in_the_graph()


# алгоритм Дейкстры
def dijkstra_algotitm_for_exercise(s: int, f: int, g: dict) -> int:
    minimum_time = dict()  # создаём словарь, в который мы будем вписывать минимальное время для прибытия в деревни
    minimum_time[s] = 0  # для деревни, из которой мы выезжаем минимальное = 0
    q = deque([s])  # создаём очередь

    # Начало алгоритма. До тех пор, пока очередь не пуста
    while q:
        now_elem = q.popleft()  # берём элемент слева очереди
        distance_now_elem = minimum_time[now_elem]  # берём минимальную дистанцию для этого элемента
        total_distance_elem = 0  # общее время для попадания в данную деревню

        # Начало обхода. Обходим деревни и их время(вес) для выезда и попадания.
        for path, cent in g[now_elem].items():

            # Если и вхождение, и прибытие меньше времени, которое мы уже затратили! Добавляем общее время
            if cent[0] > distance_now_elem and cent[1] > distance_now_elem:
                total_distance_elem += (cent[0] - distance_now_elem) + (cent[1] - distance_now_elem)
                # Если такая вершина не была обработана или по времени она меньше добавляем
                if path not in minimum_time or minimum_time[path] > distance_now_elem + total_distance_elem:
                    minimum_time[path] = distance_now_elem + total_distance_elem
                    q.append(path)

            # Если только вход больше времени, которое мы уже затратили
            elif cent[0] > distance_now_elem:
                total_distance_elem += cent[0] - distance_now_elem
                # Если такая вершина не была обработана или по времени она меньше добавляем
                if path not in minimum_time or minimum_time[path] > distance_now_elem + total_distance_elem:
                    minimum_time[path] = distance_now_elem + total_distance_elem
                    q.append(path)

            # Если только выход больше времени, которое мы уже затратили
            elif cent[1] > distance_now_elem:
                total_distance_elem += cent[1] - distance_now_elem
                # Если такая вершина не была обработана или по времени она меньше добавляем
                if path not in minimum_time or minimum_time[path] > distance_now_elem + total_distance_elem:
                    minimum_time[path] = distance_now_elem + total_distance_elem
                    q.append(path)

            # если затраченное время больше времени вхождения и выхода, то мы попадаём туда моментально, по условию задачи
            elif path not in minimum_time or minimum_time[path] > distance_now_elem:
                minimum_time[path] = distance_now_elem
                q.append(path)
        # После прохода обнуляем общее время
        total_distance_elem = 0

    # Если можно добраться до деревни f, возвращаем мин. время для попадания в него, иначе выводим -1, по условию задачи
    return minimum_time[f] if f in minimum_time else -1


# Выполняем
print(dijkstra_algotitm_for_exercise(S, F, graph))

Ссылка на саму задачу и где я её проверяю: https://acmp.ru/index.asp?main=task&id_task=134

Проблема:

До 4 теста проходит.

Просьба: Найти ошибку, недоработку в моём коде или доказать, что он не подойдёт данной задаче или не будет работать правильно, если это так, доказать на примерах и написать свой код(в приоритете буду выбирать мой исправленный код, если он существует)

Предположение: в тесте 4 есть уникальный случай, который я не прописал.

4
  • 3
    1) добавьте в код комментариев - что происходит, что за переменные и т.д. 2) избавьтесь от индексации - распаковывайте везде кортежи в набор переменных с "говорящими названиями", чтобы не надо было думать, что такое table[2], например 3) делайте рефакторинг - постарайтесь разбить код на небольшие функции, их будет проще проверить 4) напишите набор тестов для этой задачи и оформите код так, чтобы его можно было тестировать (ввод не через input, а вызов функции с передачей ей параметров). А в таком виде как оно сейчас анализировать такой код - это для мазохистов, извините.
    – CrazyElf
    Commented 27 мар. 2023 в 9:08
  • 1
    При этом у вас уже есть в коде хорошие "говорящие" переменные, это замечательно, но нужно, чтобы весь код был таким хорошим, тогда всем, кто будет читать этот код, будет гораздо проще разобраться, что там происходит.
    – CrazyElf
    Commented 27 мар. 2023 в 9:11
  • 3
    Конечно! Сейчас добавлю комментариев и переделаю всё в функцию. Извините за неудобства) Commented 27 мар. 2023 в 9:17
  • 3
    О, так гораздо лучше код выглядит. Сам я пока занят и не смогу по сути помочь, может позже, но может кто-то ещё разберётся.
    – CrazyElf
    Commented 27 мар. 2023 в 10:33

2 ответа 2

5
  1. ошибка в отбрасывании лишних ребёр. вы должны хранить все рёбра (иначе условно есть автобус 1 2 1 2 и 1 2 10 11) в вашем примере вы откинете 2 и всё остановится
  2. а как вы представляете # если затраченное время больше времени вхождения и выхода, то мы попадаём туда моментально, по условию задачи вы приехали в деревню x в момент времени 10, а оттуда автобус ушёл в 5. Как вы представляете попасть на него?)

Пример теста

1 -> 3, (1, 0, 2, 5), (2, 0, 3, 1), (2, 10, 3, 11), (1, 0, 3, 50) Я ожидаю что тут будет 11. А вывод 5.

Для исправления - храните все автобусы (их не так и много). И выбирайте тот автобус между 2 деревнями, у которого время прибытия минимально (конечно из тех, на которые не опоздали). (вы сейчас зачем-то time_leave + time_move_in складываете. Это же время прибытия а не в пути.

1
  • Учту, в особенности второе. Спасибо вам за ответ! Ждал с нетерпением. Подожду сутки, если никто больше не ответит, выберу ваш ответ в качестве правильного. Commented 29 мар. 2023 в 9:45
1
+50

Что ж, мне ваш код показался излишне громостким, поэтому я решил написать его с нуля :)

from dataclasses import dataclass


@dataclass
class Route:
    start_point: int
    start_time: int
    end_point: int
    end_time: int


def dijkstra_algorithm_for_exercise(n: int, s: int, f: int, g: list) -> int:
    if s == f: return 0   # базовая проверка на соответствие стартового и конечного пути
    time_for_travel = {m: float("inf") for m in range(1, n + 1)}  # словарь, где ключ это номер нп, а значение время до него
    all_point_list = [i for i in range(1, n + 1)]  # все нп из которых мы ещё не проверяли рейсы
    current_time = 0  # время за которое мы добирались до текущего нп
    current_point = s  # текущий населённый пункт
    for _ in range(1, n):
        # находим все рейсы, где время отправки позже или равно времени за которое мы добирались до нп
        route = [r for r in g if r.start_point == current_point and r.start_time >= current_time] 
        for trip in route:  # итерируемся по всем рейсам
            if trip.end_time < time_for_travel[trip.end_point]:  # если время прибытия в конечный нп меньше нежели время
                time_for_travel[trip.end_point] = trip.end_time  # за которое мы добирались ранее, то обновляем его

        all_point_list.remove(current_point)  # удаляем нп из списка нп в которых мы ещё не бывали
        # находим нп до которого мы можем добраться быстрее всего и при этом мы там ещё небыли
        current_point = min({key: time_for_travel[key] for key in all_point_list}, key=time_for_travel.get)
        current_time = time_for_travel.get(current_point)  # обновляем время за которое до него добирались
    # возвращаем минимальное время за которое можно добраться до нп, если оно равно "inf" возвращаем -1
    return time_for_travel.get(f) if time_for_travel.get(f) != float("inf") else -1

N = 3
S, F = 1, 3
R = 4
path_list = [Route(1, 0, 2, 5),
             Route(1, 1, 2, 3),
             Route(2, 3, 3, 5),
             Route(1, 1, 3, 10)]

print(dijkstra_algorithm_for_exercise(N, S, F, path_list))

На первый взгляд может показаться, что код стал нагромождением кучи всего, причиной этому послужило добавление комментариев почти в каждую строчку кода. Для удобства обращения с данными я так же использовал датакласс. Если будут вопросы обращайтесь, постараюсь помочь.

Update: Вот код которым я читаю и записываю данные в/из файла.

with open("input.txt", 'r') as file:
    N = int(file.readline().strip())
    S, F = map(int, file.readline().strip().split())
    R = int(file.readline().strip())
    path_list = []
    for i in range(R):
        value = map(int, file.readline().strip().split())
        path_list.append(Route(*value))

with open("output.txt", 'w') as file:
    file.write(str(dijkstra_algorithm_for_exercise(N, S, F, path_list)))
4
  • Я завтра у вас спрошу некоторые вещи, а пока пойду спать) Commented 29 мар. 2023 в 22:51
  • Ваш код не принимает система( . Только теперь не на тесте 4, как у меня, а на 2. Commented 29 мар. 2023 в 22:53
  • 1
    К сожалению, мне придёться вас разочаровать: мой код полностью работает. Ранее я не хотел регистрироваться на данном ресурсе, однако был вынужден после того, как вы сообщили, что код не работает. Вероятно, ошибка возникает при чтении данных из файла. Я обновил свой ответ и предоставил код, с помощью которого я читаю данные.
    – kristal
    Commented 30 мар. 2023 в 7:49
  • Теперь вижу, что код работает) Commented 30 мар. 2023 в 10:28

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.