← 返回题目列表

AtCoder · joi2018ho_d

D. 月票

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

配点: 100 点

JOI 在你居住的城市 有 N 个站,每个站都有 它的编号为 1, 2, \ldots, N 。另外,M 有两条铁路线,各有 它的编号为 1, 2, \ldots, M 。铁路线 i (1 \leqq i \leqq M) 是车站 A_i 和车站 B_i 双向转乘,票价为 C_i 这是日元。

JOI 君羽站 我住在 S 和车站附近 我在 T 附近的 IOI 高中就读。因此,我决定购买一张连接两者的月票。购买月票时,请前往车站 您必须指定一条在 S 和车站 T 之间行驶且票价最低的路线。使用这张月票,您可以在指定路线所包含的铁路线路上双向自由上下车。

JOI 你是站 U 和车站 我也经常去 V 附近的书店。那么,车站 U 从车站 我想购买一张通勤卡,这样前往 V 的票价就会尽可能低。 前往

駅 U 从车站 我想购买一张通勤卡,这样前往 V 时,首先前往车站。 前往 U 从车站 我想购买一张通勤卡,这样前往 V 的路线 1 选择一项。该路线包含的铁路线 在 i 支付的票价是 如果购买月票时指定的路线中包含

  • 鉄道路線 i , 如果购买月票时指定的路线不包含0 円
  • 鉄道路線 i ,C_i 円

变为。这笔费用总计为 这是前往 U 从车站 我想购买一张通勤卡,这样前往 V 的票价。购买月票时选择指定路线时的车站 我想了解前往 U 从车站 我想购买一张通勤卡,这样前往 V 所需的最低票价。

課題

购买月票时选择指定路线时的车站 编写一个程序来查找前往 U 从车站 我想购买一张通勤卡,这样前往 V 的最低票价。


入力

从标准输入读取以下输入。 写入

  • 1 行中,2 整数 N, M 。这些都在JOI居住的城市。 N 站和 M 表示有两条铁路线。 写入
  • 2 行中,2 整数 S, T 。这些是 JOI Kimiga 站 表示购买前往 S 从车站 我想购买一张通勤卡,这样前往 T 的通勤卡。 表示我们希望尽量减少前往
  • 3 行中,2 整数 U, V 。这些是 JOI Kimiga 站 表示购买前往 U 从车站 我想购买一张通勤卡,这样前往 V 所需的票价。
  • 继续 M 行中的 i 行目 (1 \leqq i \leqq M)有 写入3 整数 A_i, B_i, C_i 。这些是铁路线 i 是车站 A_i 和车站 B_i 双向转乘,票价为 C_i 代表一个圆圈。

出力

标准输出包含购买通勤卡时的车站信息。 当成功指定到 S 从车站 我想购买一张通勤卡,这样前往 T 的路线时,该站 前往 U 从车站 我想购买一张通勤卡,这样前往 V 的最低票价 1 行。 在


制限

所有输入数据满足以下条件。

  • 2 \leqq N \leqq 100\,000.
  • 1 \leqq M \leqq 200\,000.
  • 1 \leqq S \leqq N.
  • 1 \leqq T \leqq N.
  • 1 \leqq U \leqq N.
  • 1 \leqq V \leqq N.
  • S \neq T.
  • U \neq V.
  • S \neq U 或 T \neq V.
  • 从任何车站到任何其他车站 1 可使用多条铁路线到达。 对于
  • 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M).
  • 1 \leqq i < j \leqq M ,A_i \neq A_j 或 B_i \neq B_j.
  • 1 \leqq Ci \leqq 1\,000\,000\,000 (1 \leqq i \leqq M).

小課題

小課題 1 [16 点]

  • S = U 很满意。 可用于以最低票价前往

小課題 2 [15 点]

  • 駅 S 从车站 我想购买一张通勤卡,这样前往 T 的路线是 1 只有一条街。

小課題 3 [24 点]

  • N \leqq 300 很满意。 可用于以最低票价前往

小課題 4 [45 点]

  • 没有其他限制。

入力例 1

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

出力例 1

2

在本输入示例中,购买月票时可以指定的路线是车站 仅限路线 1 → 駅 2 → 駅 3 → 駅 5 → 駅 6 。 为了最大限度地减少前往

駅 1 从车站 我想购买一张通勤卡,这样前往 4 的费用,车站 您可以选择路线 1 → 駅 2 → 駅 3 → 駅 5 → 駅 4 。如果您选择这条路线,每条铁路线需支付的票价为: 连接

  • 駅 4 和车站 5 的铁路线 在 5 中,2 円.
  • 在其他铁路线上,0 円.

,所以总票价是 2 变成日元。


入力例 2

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

出力例 2

3000000000

在此输入示例中,站 请勿使用通勤卡前往 3 从车站 我想购买一张通勤卡,这样前往 6 。 给出了


入力例 3

8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8

出力例 3

15

入力例 4

5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10

出力例 4

0

入力例 5

10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16

出力例 5

19