e. 【提高】躲避拥堵的最佳路线

    Type: Default 1000ms 128MiB

【提高】躲避拥堵的最佳路线

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

小明所在的城镇有m条路连接了n个区(n个区的编号在1~n的范围内),每条大道将两个区相连接,每条大道有一个拥挤度。小明想要开车从s区去t区,请你帮他规划一条路线,使得经过道路的拥挤度的最大值最小。

输入格式

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

接下来m行,每行三个整数u,v,w,表示有一条大道连接区u和区v,且拥挤度为w。

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

数据规模与约定
对于 30% 的数据,保证n≤10。
对于 60% 的数据,保证n≤100。
对于 100% 的数据,保证1≤n≤10^4,1≤m≤2×10^4, w≤10^4,1≤s,t≤n。且从 s 出发一定能到达 t 区。

输出格式

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

样例

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

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45