← 返回题目列表

AtCoder · pakencamp_2021_day2_l

L. 之字形路径

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

配点 : 500 点

問題文

N 頂点 M 给出了一个简单的连接加权无向边图。在顶部 直到 1 减去 N 的数字位于两侧。 它们的编号最大为 1 减去 M 。侧面 i 是顶点 是 U_i 和 边缘 V_i ,重量为 W_i 。所有边的权重保证彼此不同。

頂点 1 到顶点 N 路径。按通过的边的权重顺序排列的数字序列 C = (C_1, C_2, \ldots, C_k) ,找到满足以下条件的路径:之字形路径 将其定义为。

  • C_1 < C_2 > C_3 < \cdots 或 至少 C_1 > C_2 < C_3 > \cdots 。换句话说,满足以下条件之一。
    • 任意整数 关于 i \, (1 \leq i \leq k - 1) , 当我输入 i 是奇数 C_i < C_{i+1} 和 i 是偶数 C_i > C_{i+1} 。
    • 任意整数 关于 i \, (1 \leq i \leq k - 1) , 当我输入 i 是奇数 C_i > C_{i+1} 和 i 是偶数 C_i < C_{i+1} 。

之字形路径 将其定义为存在吗?如果存在,还求经过的边的权重之和的最小值。

制約

  • 2 \leq N \leq 10^5
  • N - 1 \leq M \leq \min \left( \cfrac{N(N-1)}{2}, 10^5 \right)
  • 1 \leq U_i < V_i \leq N
  • 1 \leq W_i \leq 10^9
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • W_i \neq W_j \, (i \neq j)
  • 作为输入给出的图很简单且连通 如果
  • 所有输入均为整数

入力

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

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M

出力

之字形路径 将其定义为存在,则经过的边的权重之和的最小值为 如果 1 行输出。之字形路径 将其定义为不存在,则 -1 该值应乘以 1 行输出。


入力例 1

5 5
1 4 4
3 5 2
2 3 6
2 5 1
3 4 3

出力例 1

14

辺 1, 5, 3, 4 的顺序通过 C = (4, 3, 6, 1) 变为 通过之字形路径 将其定义为满足条件。在这种情况下,总重量是 按照 14 。

辺 1, 5, 2 顺序遵循的路径是 C = (4, 3, 2) 旁边 不是之字形路径 将其定义为。 您将收到


入力例 2

4 3
1 2 4
2 3 6
3 4 8

出力例 2

-1

入力例 3

7 12
2 5 657831697
5 6 925940778
1 2 749029915
2 4 237755672
3 6 60634766
6 7 65418621
1 4 194639839
4 7 411656898
3 7 367905753
3 4 241675120
1 6 858592389
2 6 571202751

出力例 3

562368346

原案: primenumber_zz