1923 - 躲避拥堵的最佳路线

题目描述

小明所在的城镇有 m 条路连接了 n 个区( n 个区的编号在 1 \sim n 的范围内),每条大道将两个区相连接,每条大道有一个拥挤度。

小明想要开车从 s 区去 t 区,请你帮他规划一条路线,使得经过道路的拥挤度的最大值最小。

输入

第一行有四个用空格隔开的 n,m,s,t ,其含义见题目描述。

接下来 m 行,每行三个整数 u,v,w ,表示有一条大道连接区 u 和区 v ,且拥挤度为 w ,道路为双向道路,两个方向都可以走。

两个区之间可能存在多条大道。

数据规模与约定

对于 30\% 的数据,保证 n \le 10

对于 60\% 的数据,保证 n \le 100

对于 100\% 的数据,保证 1 \le n \le 10^41 \le m \le 2 \times 10^4, w \le 10^4,1 \le s,t \le n

且从 s 出发一定能到达 t 区。

输出

输出一行一个整数,代表最大的拥挤度。

样例

输入

3 3 1 3
1 2 2
2 3 1
1 3 3

输出

2
来源

二分答案 并查集

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 2108
通过人数 1047
金币数量 3 枚
难度 提高


上一题 下一题