Задача:
Ограничение по времени: 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 есть уникальный случай, который я не прописал.
table[2]
, например 3) делайте рефакторинг - постарайтесь разбить код на небольшие функции, их будет проще проверить 4) напишите набор тестов для этой задачи и оформите код так, чтобы его можно было тестировать (ввод не черезinput
, а вызов функции с передачей ей параметров). А в таком виде как оно сейчас анализировать такой код - это для мазохистов, извините.