20C. Dijkstra?

graphs, shortest paths, *1900, https://codeforces.com/problemset/problem/20/C

You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.

Input

The first line contains two integers n and $m (2 \leq n \leq 10^{5}, m \leq 10^{5})$ , where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form ai, bi and wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 10^6^), where ai, bi are edge endpoints and wi is the length of the edge.

It is possible that the graph has loops and multiple edges between pair of vertices.

Output

Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.

Examples

input

output

1 4 3 5

input

output

1 4 3 5

使用 Dijkstra 算法 来找到从 节点 1 到节点 n 的最短路径。我们使用 优先队列 (heapq) 来高效地找到当前最短路径的扩展方式。436ms AC。

python

import sys
import heapq

def dijkstra(n, edges):
    # 使用列表存储图，减少内存开销
    graph = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 直接使用数组，避免字典占用过多内存
    INF = float('inf')
    dist = [INF] * (n + 1)
    prev = [-1] * (n + 1)
    dist[1] = 0
    
    pq = [(0, 1)]  # (当前路径长度, 当前节点)
    
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                prev[neighbor] = node
                heapq.heappush(pq, (new_dist, neighbor))
    
    if dist[n] == INF:
        return [-1]
    
    path = []
    node = n
    while node != -1:
        path.append(node)
        node = prev[node]
    
    return path[::-1]

def main():
    n, m = map(int, sys.stdin.readline().split())
    edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    print(*dijkstra(n, edges))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)  # 确保不会因为递归深度限制崩溃
    main()

构建图的邻接表：
用列表存储图（代替 defaultdict(list)），支持多条边和环。
Dijkstra 算法：
使用 最小堆 (heapq) 维护当前探索到的最短路径。
dist 记录从 节点 1 到各节点的最短距离，初始化 dist[1] = 0。
prev 记录路径中每个节点的前驱，用于路径回溯。
dist 和 prev 用数组（避免字典带来的额外开销）。
路径回溯：
从终点 n 回溯 prev 直到 1，然后反转路径。
时间复杂度
O((n + m) log n)，适用于 n, m ≤ 10⁵。

Memory limit exceeded on test 31

python

import sys
import heapq
from collections import defaultdict

def dijkstra(n, edges):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 最短路径初始化
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[1] = 0
    prev = {i: None for i in range(1, n + 1)}
    
    # 优先队列 (min-heap)
    pq = [(0, 1)]  # (当前路径长度, 当前节点)
    
    while pq:
        d, node = heapq.heappop(pq)
        
        if d > dist[node]:
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                prev[neighbor] = node
                heapq.heappush(pq, (new_dist, neighbor))
    
    # 反向构造路径
    if dist[n] == float('inf'):
        return [-1]
    
    path = []
    node = n
    while node is not None:
        path.append(node)
        node = prev[node]
    
    return path[::-1]

def main():
    n, m = map(int, sys.stdin.readline().split())
    edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    print(*dijkstra(n, edges))

if __name__ == "__main__":
    main()

python

# 主要步骤就是：先初始化，然后添加边和节点，然后运行Dijkstra算法，最后输出最短路径
from heapq import *
 
INF = 1 << 60 # 定义一个大数I作为初始化距离
 
n, m = map(int, input().split())
g = [[] for _ in range(n)]
d = [0] + [INF] * n # 初始距离全部设置为大数I，但是以0号节点为起点的距离为0
p = [-1] * n # 记录每一个节点的上一个节点，-1表示这个节点没有上一节点
q = [(0, 0)] # 把起点添加到优先队列q中
for _ in range(m): # 根据输入的边和权重构造邻接表
	u, v, w = map(int, input().split())
	g[u-1] += [(w, v-1)]
	g[v-1] += [(w, u-1)]
while q: # 只要优先队列不为空，就取出队列顶部的节点，查找它的邻接节点，如果通过这个节点到
            #邻接节点的距离比原先记录的短，就更新邻接节点的最短距离并加入优先队列
	u = heappop(q)[1]
	for e in g[u]:
		w, v = d[u] + e[0], e[1]
		if w < d[v]:
			d[v], p[v] = w, u
			heappush(q, (d[v], v))
if d[n-1] == INF: # 如果终点的最短距离仍然是I，表示不存在从起点到终点的路径
	print(-1);
else:
	x, a = n - 1, []
	while x != -1: # 按上一个节点的信息，从终点倒推到起点，得到最短路径
		a += [x + 1]
		x = p[x]
	a.reverse() # 因为得到的路径是反向的，所以需要反转一下
	print(' '.join(map(str, a)))

20C. Dijkstra? ​

20C. Dijkstra?