Алгоритм Форда-Беллмана - 2
(Время: 1 сек. Память: 16 Мб Сложность: 44%)
В ориентированном взвешенном графе вершины пронумерованы числами от 1 до N. Если i < j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле:
w(i,j) = (179∙i+719∙j) mod 1000 – 500
Определите вес кратчайшего пути, ведущего из вершины 1 в вершину N.
Входные данные
Входной файл INPUT.TXT содержит целое число N (2 ≤ N ≤ 104).
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число – вес кратчайшего пути из вершины 1 в вершину N в описанном графе.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 | 117 |
| 2 | 3 | -164 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
