Статья Нахождение K-го кратчайшего пути

Прочитайте статью внимательнее. Там хорошо объяснено почему именно такая асимптотика.
Вы говорите про факториал, т.е. это количество всех возможных путей. Но в этом алгоритме мы не пройдем путей больше чем K. Этот нюанс специально контролируется тем, что мы не идем в те вершины, для которых предпросчитанное Дейкстрой расстояние больше чем надо.

Вы же говорите про вариант, когда К у нас близок к факториалу, т.е. надо найти один из самых длинных путей, в этом случае алгоритм действительно будет работать долго.
Но и здесь асимптотика описана верно, поскольку K становится примерно равным N!

Хмм, а ведь и правда фигня какая-то получается Всё дело в том, что условие "curlen + len + dist[to] <= maxlen" не гарантирует нам, что мы действительно найдём хотя бы один подходящий путь, если пойдём в to. Потому что вершины в пути не могут повторяться, а заранее выполненная Дейкстра ничего об этом не знала. Пример Olegа это демонстрирует.

Понятно, как исправить это с ухудшением асимптотики: на каждом уровне рекурсии после строки "used[v] = true;" выполнять Дейкстру из t во все вершины, но при этом все поюзанные вершины запретить; соответственно, в цикле по to ниже использовать эти только что вычисленные расстояния. Тем самым мы сможем гарантировать, что после захода в вершину to хотя бы один путь в t найдётся, и тогда алгоритм будет работать полиномиально. Но при этом, понятно, вся асимптотика умножится на время выполнения Дейкстры, что не очень хорошо.

В любом случае, в статье и правда серьёзная идейная ошибка, спасибо Olegу. Можно ещё попробовать подумать, как решить эту задачу без такого ухудшения асимптотики, а потом тогда я исправлю и статью.

P.S. Интересно, как тогда у меня этот код прошёл по задаче (где n<=100) в одном из problemsetов...