timus 1527

Пусть нам известна высота нашей машины. Как тогда узнать, можно ли проехать за данную стоимость и не превысив данное время? Так как стоимость каждой дороги равна 1, мы можем для каждой вершины находить минимальное время за которое мы можем доехать до данной вершины, проехав ровно по К приватным дорогам. Тогда построим граф, где каждой вершиной будет пара - номер вершины в исходном графе и К. Вершин в таком графе будет N*N, т.к. нам не нужно проезжать более чем по N дорогам. Ребра будут идти между смежными вершинами, если требуемая высота не превышает данную, причем если дорога цены 0, тогда у вершин будет одинаковое К, иначе отличное на 1. Можно запустить алгоритм дейкстры на таком графе для нахождения кратчайшего пути от (S,0) до (T,K), где K - любое от 0 до min(N,money). Тогда если наименьшее время до хотя бы одной такой вершины не превышает maxtime, то при данной высоте проехать можно, иначе нельзя.
Ну а чтобы найти нужную высоту машины просто сделаем бинарный поиск.