Входные данные
Первая строка входных данных содержит два числа: 𝑛 (2≤𝑛 ≤2⋅10^5) и 𝑚 (1≤𝑚≤4⋅10^5) — количество поселений в империи и количество дорог в ней.
Следующие 𝑚 линии описывают дороги между населенными пунктами. Каждая дорога описывается тремя числами: 𝑣, 𝑢 (1≤𝑣,𝑢,≤𝑛,𝑣≠𝑢) и 𝑤 (1≤𝑤≤10^9). Это означает, что между точками с номерами 𝑣 и 𝑢 есть дорога, длина которой равна 𝑤.
Вывод
Первая строка выходного файла должна содержат одно натуральное число 𝑘 (2≤𝑘≤𝑛) — количество населенных пунктов на кратчайшем пути от населенного пункта 1 до населенного пункта 𝑛.
Во второй строке через пробел выведите поселения на кратчайшем пути от 1 до 𝑛 в порядке обхода, включая сами 1 и 𝑛.
Если пути от 1 до 𝑛 нет, то выведите −1. В этом случае вы можете начать беспокоиться за жизнь кучера.
Если ответов несколько, выведите любой.
ограничение по времени для теста: 1 секунда
Ограничение памяти на тест: 256 мегабайт
Код: Выделить всё
import heapq
import sys
def dijkstra(graph, start, end):
n = len(graph)
distances = [float('inf')] * n
distances[start] = 0
prev = [-1] * n
pq = [(0, start)]
while pq:
dist, u = heapq.heappop(pq)
if u == end:
path = [end]
while prev[path[-1]] != -1:
path.append(prev[path[-1]])
path.reverse()
return dist, path
for v, w in graph[u]:
if dist + w < distances[v]:
distances[v] = dist + w
prev[v] = u
heapq.heappush(pq, (distances[v], v))
return -1, []
#input data
n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n)]
for _ in range(m):
v, u, w = map(int, sys.stdin.readline().split())
graph[v-1].append((u-1, w))
graph[u-1].append((v-1, w))
# Dijkstra func
distance, path = dijkstra(graph, 0, n-1)
# Outout
if distance == -1:
sys.stdout.write("-1\n")
else:
sys.stdout.write(str(len(path)) + "\n")
sys.stdout.write(" ".join(str(x+1) for x in path) + "\n")
Я уже сделал оптимизацию, которая работает в 2 раза быстрее той, с которой я начал, но их гораздо больше. впереди еще больше оптимизации.
Я исследовал около 10 дней и уже прочитал много статей по этой теме, но либо я не понимаю, как реализовать, либо это просто оптимизация
Я выбрал алгоритм Дейкстры как классический способ решения такого рода задач.
После исследования способов реализации я выбрал кучу как самый быстрый из рекомендованных.
Также попробовал другие способы сбора пути.
Также изменил ввод-вывод на sys.stdout и получил некоторые преимущества в скорости, но все равно недостаточно
*
Может есть лучший алгоритм для его задачи? Или это просто проблема неправильной оптимизации? *
Ввод
5 5
1 2 1
2 3 6
3 4 7
4 5 10
1 4 3
1 3 4
Выход 3
1 4 5
Вход
8 9
1 2 4
2 3 6
3 1 5
1 4 5
1 5 5
5 4 7
5 6 1
6 7 1
7 8 1
Вывод
5
1 5 6 7 8
Ввод
5 4
1 2 5
1 3 5
2 3 1
4 5 1
Вывод
Подробнее здесь: https://stackoverflow.com/questions/784 ... timisation
