← 返回题目列表

AtCoder · tessoku_book_ek

B64. 带恢复的最短路径

中文机器翻译题面 查看原题

配点: 1000 点

問題文

頂点数 N、辺数 M 的加权无向图。 顶点 来自 1 的顶点 查找到 N 的具体最短路线 1 请输出一个。 计算量为 优选 O(M \log N) 。

制約

  • 2 \leq N \leq 100000
  • 1 \leq M \leq \min(100000,N(N-1)/2)
  • 1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
  • 1 \leq C_i \leq 10000\ (1\leq i\leq M)
  • i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
  • 在给定的图中,顶点 1 和顶点 这意味着 N 是一个串联
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

按以下格式回答 1 行输出。

v_1 v_2 \cdots v_k

(v_1,v_2,\ldots,v_k) 是给定图中的顶点 必须是到 1 的顶点 查找到 N 的最短路径。 正式地,(v_1,v_2,\ldots,v_k) 必须满足的条件如下。

  • v_1=1,v_k=N
  • 给定的图有边 (v_i,v_{i+1}) 存在 (1\leq i\lt k)
  • 以上 2 满足什么样的条件 同样对于 (u_1,u_2,\ldots,u_l) ,边缘 (v_i,v_{i+1}) 的长度之和是边 小于或等于 (u_i,u_{i+1}) 的长度总和

入力例 1

6 7
1 2 15
1 4 20
2 3 65
2 5 4
3 6 50
4 5 30
5 6 8

出力例 1

1 2 5 6

给定图中的顶点 到 1 的顶点 查找到 N 的最短路径是:


入力例 2

15 30
10 11 23
11 13 24
5 8 22
10 15 18
12 14 15
2 10 11
4 7 15
5 7 15
7 9 8
8 12 1
5 14 1
10 14 17
10 12 11
8 10 6
7 14 28
6 9 1
1 10 19
4 5 4
9 10 21
7 10 21
4 10 29
5 10 8
4 14 8
11 12 24
10 13 13
3 10 1
5 12 24
2 15 23
6 10 18
6 15 25

出力例 2

1 10 15