D. Кратчайший путь в ациклическом графе
1000 мс · 256 МБ · всё или ничего
Дан ориентированный ациклический граф со взвешенными рёбрами. Веса могут быть отрицательными. Найдите длину кратчайшего пути из в .
Формат ввода
В первой строке - числа , , , (, ).
В следующих строках - тройки , , : ребро из в длины (). Граф ациклический и не содержит петель.
Формат вывода
Выведите длину кратчайшего пути из в или слово Unreachable, если пути нет.
Примеры
ввод
2 1 1 2 1 2 -10
вывод
-10
ввод
3 1 1 3 1 2 7
вывод
Unreachable
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.