Masala D
Минимальное Максимальное Ребро
Дан взвешенный связный неориентированный граф и отмечены две вершины s и t. Найдите минимальное максимальное ребро на пути из вершины s в вершину t.
В первой строке заданы четыре целых числа через пробел: , , , (, ) - количество вершин в графе, количество рёбер в графе и номера начальной и конечной вершин пути соответственно.
В следующих строках описаны рёбра графа. Каждая строка содержит три целых числа через пробел: , , () - вершины, которые соединяет ребро, и его вес.
Выведите одно число - вес минимального максимального ребра на пути из вершины в вершину .
# | input.txt | output.txt |
---|---|---|
1 |
5 7 1 5 2 5 2 1 2 5 3 1 5 4 5 6 3 2 3 2 4 4 5 1 10 |
5 |
В примере существует множество путей из 1 в 5. Рассмотрим путь 1 → 2 → 5. В этом пути максимальное ребро веса 5. Заметим, что нет пути из 1 в 5 с меньшим максимальным ребром.