Минимальный путь в графе с несколькими ограничениями.

1) Если это задача с олимпиады, то ограничения какие? (на количество вершин, количество ребер, и вес ребер)
Ну а если просто себе придумал задачку, тогда тут сложнее дело обстоит

2) Путь любой вообще? Или между двумя заданными вершинами?

Кстати сразу паралельно возникла еще одна похожая задача.
Тоже есть граф такой же самый, но надо построить каркас с максимальным значением на ребрах не больше Ma и Mb.

НУ тупое решение этих двух задач такое:
Всех возможных наборов a -  b столько сколько ребер. Т.е. M^2
Для всех возможных M^2 вариантов, выкидываем ребра из графа и пытаемся на нем найти в нем ответ, за N^2
сложность в результате O(M^2 * N^2) что обычно не очень гут

Можно ускорить выкидывая для каждого фиксированого А бинарным поиском выкидывать В.
Тогда вариантов будет M*logM и каждый решать за N^2

Результат O(N^2 * M*logN) но подозреваю что это тоже не очень гут

Но меньшей оценки пока не придумал.
А вообще задачка интересная...

Сделаем бинпоиск по высоте.

Стоимости дорог 0 или 1, поэтому как бы мы не ехали - самый дорогой путь будет не дороже чем 100. Значит, можем построить новый граф, где вершинами будут пары (номер,стоимость дороги сюда). Запустим алгоритм Дейкстры по этому графу, минимизируя суммарное время проезда. Затем просто проверим для всех подходящих пар (конечная вершина, стоимость не больше допустимой) времена, требуемые чтобы достигнуть такой пары. Если подходящее есть - говорим что такая высота нам подходит, иначе говорим что не подходит.

AC, но дейкстра с set-ом работают аж 1.406...

всем спасибо:)