← 返回题目列表

AtCoder · awc0074_d

D. 安全上学路线

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

分数: 400 分

问题陈述

高桥每天从家步行到学校。最近,在他上学路线的某个地点附近发现了一只流浪狗。流浪狗以特定地点为基地,并在其附近漫游。

高桥想要选择一条距离流浪狗基地尽可能远的路线。

该镇包括 N 点和 M 双向道路。每个点的编号从 1 to N。每条路 i (1 \leq i \leq M) 连接点 U_i 和点 V_i,并采取 W_i 穿越分钟 (W_i 是正整数)。

高桥的家就在这儿 S,他的学校现在在 T,流浪狗的基地在点 P.

的 最短行程时间 d(X) 来自流浪狗基地的点 P 到一点 X 定义如下:

  • d(P) = 0.
  • 当点 X (X \neq P) 可以从点到达 P, d(X) 是最短行程时间(总和 W_i 所经过的道路)从点开始的所有路径 P 点 X.
  • 如果点 X 无法从点到达 P,那么 d(X) = +\infty.

在这里, +\infty 被认为大于任何有限值。

A 简单路径 从点 S 点 T 是一系列点 v_0, v_1, \ldots, v_k (其中 k \geq 1, v_0 = S, v_k = T) 满足以下所有条件:

  • v_0, v_1, \ldots, v_k 都是不同的(没有点被访问超过一次)。
  • 对于所有 1 \leq j \leq k,存在道路连接点 v_{j-1} 和点 v_j.

的 安全评分 简单路径 v_0, v_1, \ldots, v_k 定义为最小值 d 路径上的所有点,包括起点和终点,即:

\min(d(v_0), d(v_1), \ldots, d(v_k))

这里,如果 d 包括有限值和 +\infty, \min 取有限值中的最小值。安全得分为 +\infty 仅当所有 d(v_j) 是 +\infty.

安全得分表示沿路线距离流浪狗基地最近的点距该基地的距离。

在从点开始的所有简单路径中 高桥可以选择的 S 点 T ,找到最大的安全分数。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S, T, P \leq N
  • S \neq T
  • S 和 P,以及 T 和 P,可能一致
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
  • 至多有一条道路连接任意一对点
  • 从点出发至少存在一条简单路径 S 点 T
  • 所有输入值均为整数

输入

N M
S T P
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 第一行包含点数 N 和道路数量 M,用空格分隔。
  • 第二行包含点号 S 高桥家,点数 他的学校的 T 以及点数 流浪狗基地的 P ,以空格分隔。
  • 以下 M 行(来自行 3 转线 M + 2) 给出每条道路的信息。
  • 的 (2 + i)第行 (1 \leq i \leq M) 包含两点 U_i, V_i 有公路相连 i 和遍历时间 W_i,用空格分隔。

输出

在一行中输出高桥可以选择的所有简单路径中的最大安全分数。

如果最大安全分数是 +\infty,即如果存在一条简单路径,该路径上的所有点都无法从点到达 P,输出 INF 。

否则,最大安全分数是非负整数。输出该值。


示例输入 1

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

示例输出 1

1

示例输入 2

4 3
1 2 4
1 2 1
1 3 2
2 3 3

示例输出 2

INF

示例输入 3

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

示例输出 3

4

示例输入 4

12 16
1 12 6
1 2 3
2 3 4
3 6 2
6 12 1
1 4 5
4 5 3
5 9 2
9 10 4
10 11 3
11 12 2
4 8 6
8 12 7
2 7 1
7 11 5
5 6 8
8 9 1

示例输出 4

1

示例输入 5

2 1
1 2 1
1 2 1000000000

示例输出 5

0