В решении задачи 144D некоторые участники использовали алгоритм, известный под названием алгоритм Левита (на английском попадается под названием SPFA).
Хочу поделиться тестом, который заваливает все найденные мною сабмиты с той или иной модификацией этого алгоритма.
Тест:
n 2*n-3 1
1 2 1000000000 / 2
1 3 1000000000 / 3
1 4 1000000000 / 4
....
1 n 1000000000 / n
2 3 1
3 4 1
......
n-1 n 1
l
и для случая, когда вершины в списке смежности оказываются в обратном порядке:
n 2*n-3 1
1 n 1000000000 / n
1 n-1 100000000 / n-1
...
1 2 1000000000 / 2
2 3 1
3 4 1
......
n-1 n 1
l
генератор: https://gist.github.com/1652283
сабмиты, которые заваливаются:
