题目详情题解（0）讨论（0）提交记录（0）

AT_joi2018ho_d.定期券 (Commuter Pass)

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

JOI 君居住的城市中有 NN 个车站，编号为 11 到 NN。同时，还有 MM 条铁路线，编号为 11 到 MM。每条铁路线 ii (1≤i≤M1 \leq i \leq M) 连接车站 AiA_i 和车站 BiB_i，票价为 CiC_i 日元。

JOI 君住在车站 SS 附近，学校在车站 TT 附近，因此他计划购买一张从车站 SS 到车站 TT 的定期票。购买该定期票时，需要选择一条从 SS 到 TT 的最低票价路径。购票之后，他可以在这条指定路径上的所有铁路线自由通行。

此外，JOI 君还频繁访问车站 UU 和车站 VV 附近的书店。他希望选择的定期票能帮助他降低从车站 UU 到车站 VV 的出行费用。

从车站 UU 到车站 VV 时，若经过的铁路线 ii 包含在定期票所指定的路径中，则票价为 00 日元；否则，票价为 CiC_i 日元。我们的目标是找到一种选择定期票路径的方法，使得从车站 UU 到车站 VV 的总票价最小。

输入格式

从标准输入中读取：

  • 第一行输入两个整数 NN 和 MM，分别表示车站数量和铁路线数量。
  • 第二行输入两个整数 SS 和 TT，表示欲购买定期票的起点和终点车站。
  • 第三行输入两个整数 UU 和 VV，表示希望计算票价最小化的起点和终点车站。
  • 接下来的 MM 行，每行包含三个整数 Ai,Bi,CiA_i, B_i, C_i，表示第 ii 条铁路线连接车站 AiA_i 和车站 BiB_i，票价为 CiC_i 日元。

输出格式

输出一个整数，表示通过合理选择定期票路径后，从车站 UU 到车站 VV 的最小票价。

输入输出样例

  • 输入#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

  • 输入#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

    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

说明/提示

限制

所有数据满足：

  • 2≤N≤100,0002 \leq N \leq 100,000
  • 1≤M≤200,0001 \leq M \leq 200,000
  • 1≤S,T,U,V≤N1 \leq S, T, U, V \leq N
  • S≠TS \neq T
  • U≠VU \neq V
  • S≠US \neq U 或 T≠VT \neq V
  • 任意两个车站间至少有一条可行的铁路线
  • 对于 1≤i≠j≤M1 \leq i \neq j \leq M，Ai≠AjA_i \neq A_j 或 Bi≠BjB_i \neq B_j
  • 1≤Ci≤1,000,000,0001 \leq C_i \leq 1,000,000,000

子任务

子任务 1 [16 分]

  • 满足 S=US = U。

子任务 2 [15 分]

  • 从车站 SS 到车站 TT 的最优路径唯一。

子任务 3 [24 分]

  • N≤300N \leq 300。

子任务 4 [45 分]

  • 无额外限制。

示例解释

在示例中，从车站 11 到车站 44 的最小票价路径是 1→2→3→5→41 \to 2 \to 3 \to 5 \to 4。在该路径上，除了 55 号铁路线需支付 22 日元外，其他路线均免费，总费用为 22 日元。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页