Задача: Беллман
Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).
Дана стартовая и конечная вершина, определить минимальное расстояние между ними.
Входные данные:
Дано 4 числа n, m, s, f - количество вершин, количество ребер, стартовая и конечная вершина(начиная с 1) соответственно.
В следующих m строках содержится по 3 числа - вершина 1, вершина 2 и цена перехода между вершинами.
Выходные данные:
Требуется вывести одно число - ответ на поставленную задачу. Если ответа нет - следует вывести Inf.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 2 1 4
1 2 100500
2 3 100500
|
Inf |
Ваш ответ: