所以我正在继续我的算法课程
输入数据 输入数据的第一行包含两个数字：𝑛 (2≤𝑛≤2⋅10^5) 和 𝑚 (1≤𝑚≤4⋅10^5) — 帝国的定居点数量和帝国的道路数量它。
以下𝑚线描述了定居点之间的道路。每条道路由三个数字描述：𝑣、𝑢 (1≤𝑣,𝑢,≤𝑛,𝑣≠𝑢) 和 𝑤 (1≤𝑤≤10^9)。这意味着在数字 𝑣 和 𝑢 的点之间有一条长度为 𝑤 的道路。
输出 输出文件的第一行必须包含一个自然数 𝑘 (2≤𝑘≤𝑛) — 从定居点 1 到定居点 𝑛 的最短路径上的定居点数量。
在第二行，以空格分隔，按遍历顺序打印从 1 到 𝑛 的最短路径上的聚落，包括 1 和 𝑛 本身。
如果没有从1到𝑛的路径，则输出−1。在这种情况下，你可能会开始担心车夫的生活了。
如果有多个答案，请打印其中一个。
测试时间限制：1秒 每个测试的内存限制：256 MB
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天，并且已经阅读了很多关于这个主题的文章，但要么我不明白如何实施，要么它只是优化
我选择Dijkstra算法作为解决此类问题的经典方法。
在研究了实现方式之后，我选择堆作为最快的推荐。 还尝试了其他方法来收集路径。
还将输入输出更改为 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
由于我们没有任何东西可以测试，这将是在黑暗中进行的尝试，但是如果您使用双向 Dijkstra 搜索，您可以获得一些运行时间增益。
以下是该想法的可能实现：
from heapq import heappop, heappush
from dataclasses import dataclass
@dataclass
class ShortestPath:
distance = float("inf")
node_on_path = None
class DijkstraState:
def __init__(self, graph, start, shortest: ShortestPath):
n = len(graph)
self.graph = graph
self.distances = [float('inf')] * n
self.distances[start] = 0
self.prev = [-1] * n
self.pq = [(0, start)]
self.opposite_distances = []
self.shortest = shortest
def process_next(self):
dist, node = heappop(self.pq)
if dist == self.distances[node]:
for neighbor, weight in self.graph[node]:
neighbor_dist = dist + weight
if neighbor_dist < self.distances[neighbor]:
self.distances[neighbor] = neighbor_dist
self.prev[neighbor] = node
heappush(self.pq, (neighbor_dist, neighbor))
total_distance = neighbor_dist + self.opposite_distances[neighbor]
if total_distance < self.shortest.distance:
self.shortest.distance = total_distance
self.shortest.node_on_path = neighbor
return dist
def get_path_to_start(self):
node = self.shortest.node_on_path
while node != -1:
yield node
node = self.prev[node]
def dijkstra(graph, start, end):
if start == end: # Boundary case
return [start]
shortest = ShortestPath() # mutable object to record shortest of inspected paths
forward = DijkstraState(graph, start, shortest)
backward = DijkstraState(graph, end, shortest)
# Each gets a reference the distances found in the other direction
forward.opposite_distances = backward.distances
backward.opposite_distances = forward.distances
while forward.pq and backward.pq:
distance = forward.process_next() + backward.process_next()
if distance >= shortest.distance: # Sure to have found the shortest path
path = list(forward.get_path_to_start())[:0:-1]
path.extend(backward.get_path_to_start())
return path
return [] # No path found
注意：如您所见，这不会返回距离。我认为你不需要它。要知道何时输出-1，只需查看返回的路径为空即可：
# ...
# ...
# Dijkstra func
path = dijkstra(graph, 0, n-1)
# Outout
if not path:
print("-1")
else:
print(len(path))
print(" ".join(str(x+1) for x in path))