分数: 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