← 返回 google 的题目列表Minimum Required Safety Value in a Weighted Graph Under a Threshold
类型：online_judge
Problem: Minimum Required Safety Value in a Weighted Graph Under a Threshold
You are given an undirected weighted graph with n nodes numbered from 0 to n - 1 and m edges. Each edge (u, v, w) means there is an edge between u and v with safety value w.
You are also given:
a starting node source
an ending node target
a safety threshold threshold
You need to travel from source to target. Every edge on the path must satisfy:
w < threshold
For a valid path, its required safety value is defined as the maximum edge weight along that path.
Return the minimum possible required safety value among all valid paths from source to target.
If no such path exists, return -1.
If source == target, return 0.
Input Format
n m source target threshold
u1 v1 w1
u2 v2 w2
...
um vm wm
Output Format
answer
Constraints
1 <= n <= 2 * 10^5
0 <= m <= 2 * 10^5
0 <= source, target < n
0 <= wi <= 10^9
0 <= threshold <= 10^9
The graph is undirected
Nodes are 0-indexed
Example
Input
4 4 0 3 10
0 1 5
1 3 7
0 2 3
2 3 8
Output
7