Напишите код на любом языке программирования пожалуйста!!
Гоа'улд Апофис снова захватил команду Джека О'Нила! Сам Джек смог спастись, но к тому времени корабль Апофиса уже совершил прыжок в гиперпространство. Однако Джек знает, на какой планете высадится Апофис. Чтобы спасти друзей, Джеку предстоит несколько раз пройти через звездные врата, чтобы попасть на эту планету.
Всего в галактике находится n планет, пронумерованных числами от 1 до n. Джек находится на планете с номером 1, а Апофис высадится на планете с номером n. Между некоторыми парами планет можно перемещаться через звездные врата (перемещение возможно в обоих направлениях); перемещение занимает положительное и, возможно, для разных пар планет неодинаковое количество секунд. Джек начинает свое путешествие в момент времени 0.
Может оказаться, что на планету, где сейчас находится Джек, через звездные врата прибывают другие путешественники, в этом случае Джек должен подождать ровно 1 секунду, прежде чем сам сможет воспользоваться звездными вратами. То есть, если в момент времени t на планету прибывает другой путешественник, то Джек может пройти через врата только в момент времени t + 1, если только в момент времени t + 1 на ту же планету не прибывают еще путешественники.
Зная информацию о времени перемещения между планетами, а также о моментах времени, когда Джек не сможет пользоваться звездными вратами на конкретных планетах, определите наименьшее время, за которое он сможет попасть на планету с номером n.
Входные данные
Первая строка содержит два целых числа, разделенные пробелом: n (2 ≤ n ≤ 105), количество планет в галактике, и m (0 ≤ m ≤ 105), количество пар планет, между которыми можно перемещаться сквозь звездные врата. Далее следуют m строк, в каждой из них содержится три целых числа: i-ая строка содержит номера планет ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), между которыми есть связь через звездные врата, и целочисленное время (в секундах) перемещения между этими планетами ci (1 ≤ ci ≤ 104). Гарантируется, что между любой парой планет существует не более одного перехода, образованного звездными вратами.
Далее следуют n строк: i-тая строка содержит целое число ki (0 ≤ ki ≤ 105), которое обозначает количество моментов времени, в которые на планету с номером i прибывают другие путешественники. Далее через пробел следуют ki упорядоченных по возрастанию различных целых чисел tij (0 ≤ tij < 109). Число tij обозначает, что в момент времени tij (в секундах) на планету i прибывает другой путешественник. Гарантируется, что сумма всех ki не превышает 105.
Выходные данные
Выведите единственное число — наименьшее количество времени, которое понадобится Джеку, чтобы попасть с планеты 1 на планету n. Если Джек не сможет попасть на планету n ни за какое время, выведите число -1.
import heapq
import sys
# Read input
input_data = sys.stdin.read().split()
it = iter(input_data)
try:
# Read n and m
n = int(next(it))
m = int(next(it))
# Build adjacency list
adj = [[] for _ in range(n + 1)]
for _ in range(m):
a = int(next(it))
b = int(next(it))
c = int(next(it))
adj[a].append((b, c))
adj[b].append((a, c))
# Read forbidden times
F = [set() for _ in range(n + 1)]
for v in range(1, n + 1):
ki = int(next(it))
for _ in range(ki):
t = int(next(it))
F[v].add(t)
# Dijkstra's algorithm with waiting time
dist = [float('inf')] * (n + 1)
dist[1] = 0
PQ = [(0, 1)] # (arrival_time, planet)
heapq.heapify(PQ)
visited = [False] * (n + 1)
while PQ:
arrive_u, u = heapq.heappop(PQ)
if visited[u]:
continue
visited[u] = True
# Calculate earliest departure time
depart_u = arrive_u
while depart_u in F[u]:
depart_u += 1
# Update neighbors
for v, c in adj[u]:
arrive_v = depart_u + c
if arrive_v < dist[v]:
dist[v] = arrive_v
heapq.heappush(PQ, (arrive_v, v))
# Output result
if dist[n] == float('inf'):
print(-1)
else:
print(int(dist[n]))
except (StopIteration, ValueError):
# If input is incomplete or invalid, output -1
print(-1) Описание решения
Для решения задачи разработан Python-код, который использует модифицированный алгоритм Дейкстры. Алгоритм учитывает, что Джек должен ждать, если в момент, когда он хочет отправиться через звездные врата, на планете появляется другой путешественник. Код эффективно обрабатывает входные данные с количеством планет и связей до 10^5, а также списки запрещенных времен отправления.
Как работает код
Чтение данных: Входные данные считываются быстро с помощью sys.stdin.read (), чтобы обработать большие объемы информации.
Построение графа: Создается список смежности, где для каждой планеты хранятся соседние планеты и время перехода к ним.
Хранение запрещенных времен: Для каждой планеты запрещенные времена отправления хранятся в множестве для быстрого поиска.
Алгоритм Дейкстры:
Используется очередь с приоритетами для выбора планеты с минимальным временем прибытия.
Для каждой планеты вычисляется ближайшее время отправления, начиная с времени прибытия, пропуская запрещенные моменты.
Обновляются времена прибытия для соседних планет, если найден более быстрый путь.
Вывод результата: Если до планеты n добраться невозможно, выводится -1; иначе выводится минимальное время прибытия.
.
Это не самая простая задача на поиск пути в графе. Читайте про поиск в глубину (позволяет узнать, возможно ли вообще из узла А попасть в узел Б) и поиск в ширину (позволяет найти кратчайший маршрут), - это поможет понять, как сделать программу.
Могу, например, порекомендовать книгу Р. Седжвика "Фундаментальные алгоритмы на Си++".