配点 : 900 点
問題文
2 在维度平面上, 编号至1 它们的编号最大为 N 编号最多为 N 个国家。 国家 i 是坐标 它位于 (X_i,Y_i) 。
每个国家都有自己的航空公司。 国家 i 航空公司是 一切满足X_j \leq X_i 和 Y_j \leq Y_i 所有相遇的人 j (j \neq i), 国家 j 之间有直飞航班。 该直飞航班是双向的。 换句话说,国家 i 飞往 该国 的航班 i 来自国家/地区 您还可以移至 j 国家 您也可以移至 j 来自国家/地区 您还可以移至 i 。 国家 i 航空公司的飞机是1 每次使用时 C_i 将收取 100 日元的费用。
Ken 目前在该国 S 在国内 我想转到 T 。 乘飞机旅行时,求飞机的最低总费用。
制約
- 2 \leq N \leq 10^5
- 0 \leq X_i \leq 10^9
- 0 \leq Y_i \leq 10^9
- 1 \leq C_i \leq 10^9
- (X_i,Y_i) \neq (X_j,Y_j) (i \neq j)
- 1 \leq S \leq N
- 1 \leq T \leq N
- S \neq T
- 仅乘坐飞机前往该国 您可以向上移动到 S 来自国家/地区 您还可以移至 T 。
- 所有输入值都是整数。 打印前往
入力
输入是按以下格式从标准输入给出的。
N S T X_1 Y_1 C_1 X_2 Y_2 C_2 \vdots X_N Y_N C_N
出力
国 S 来自国家/地区 您还可以移至 T 时的最低飞机票价总额。
入力例 1
4 1 4 0 1 3 1 1 6 0 0 4 1 0 8
出力例 1
11
在本例中,直飞航班是 5 类型存在。
- 国 1 和国家 连接 3 的直达航班。国家 它由 1 航空公司运营,一旦您使用它, 3 花费日元。 如果您想要前往
- 国 1 和国家 连接 2 的直达航班。国家 它由 2 航空公司运营,一旦您使用它, 6 花费日元。 如果您想要前往
- 国 2 和国家 连接 3 的直达航班。国家 它由 2 航空公司运营,一旦您使用它, 6 花费日元。 如果您想要前往
- 国 2 和国家 连接 4 的直达航班。国家 它由 2 航空公司运营,一旦您使用它, 6 花费日元。 如果您想要前往
- 国 3 和国家 连接 4 的直达航班。国家 它由 4 航空公司运营,一旦您使用它, 8 花费日元。 如果您想要前往
国 1 来自国家/地区 您还可以移至 4 ,请单击国家/地区 如果您移动到 1→3→4 ,则总费用将为 11 变成一个圆圈,这是最小的。
入力例 2
9 3 6 2 3 9 1 4 2 0 4 16 1 3 77 3 3 12 4 0 96 4 2 41 2 1 17 3 4 45
出力例 2
104