B64 - Shortest Path with Restoration Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 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