K. Сколько рёбер в длиннейшем пути
3000 мс · 256 МБ · всё или ничего
Как классная задача K, но выведите вес длиннейшего пути и количество рёбер в нём. Если путей наибольшего веса несколько, возьмите тот, где рёбер меньше всего.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с рёбрами: начало, конец и вес (). Граф ациклический.
Формат вывода
Два числа: вес длиннейшего пути из 1 в и количество рёбер, или , если пути нет.
Примеры
ввод
4 5 1 2 5 2 4 5 1 3 1 3 4 1 1 4 10
вывод
10 1
ввод
2 0
вывод
-1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.