Условие задачи:
Сеть провайдеров состоит из N узлов и M оптоволоконных линий связи между парами узлов. Передача данных по оптоволоконной линии может осуществляться по обе стороны. Любые два узла соединены не более чем одной оптоволоконной линией. Для каждой оптоволоконной линии известно время прохождения сигнала по ней, измеряемое в наносекундах. Инженеры провайдера подготовили K предложений о прокладке новых оптоволоконных линий, каждое предложение имеет вид "строительство линии о узла U до узла V со временем
прохождения сигнала T будет стоить C бурлей" . При этом если узлы U и V уже были соединены в исходной сети, то предложений о строительстве новой линии между ними гарантированно не было подготовлено.
В связи с развитием облачного гейминга возросли требования к скорости прохождения сигнала от узлов, рядом с которыми размещены
сервера до мест скопления геймеров. В частности было сформировано P требований "время прохождения сигнала от узла A до узла B не должно превосходить T наносекунд"
Определите, какие из предложений о строительстве нужно удовлетворить, чтобы выполнялись все требования.
Формат ввода
В первой строке записаны числа N (1 <= N<= 100) и m( 0 <= M <= 10 000) - количество узлов и уже существующий оптоволоконных линий.
Следующие M строк содержат описание оптоволоконных линий. Каждое описание состоит из трех целых чисел U,V,T(1<=U,V<=N,U != V,1<=T<=10000) - номеров соединяемых линией узлов и времени прохождения сигнала в наносекундах.
В следующей строке записано число K - количество предложений о строительстве новых линий.
Следующие K строк содержат описание предложений. Каждое описание состоит из четырех целых чисел U,V,T и C - номера соединяемых узлов, время прохождения сигнала и стоимость постройки линии соответственно.
В следующей строке записано число P - количество требований.
Следующие P строк содержат описание требований. Каждое описание состоит из трех целых чисел
A,B и T - номера узлов и максимально допустимое время прохождения сигнала между ними.
Формат вывода
Выведите количество предложений о строительстве, которые необходимо удовлетворить.
В следующей строке выведите номера предложений, которые необходим удовлетворить, в порядке возрастания.
Предложения нумеруются как во входных данных начиная с единицы. Минимизируйте стоимость строительства самой дорогой построенной предложенной линии.
Если удовлетворить требования невозможно выведите -1.
Если все требования удовлетворены без строительства выведите 0
Не понятно с примером 2. Я думал, что необходимо найти минимальную стоимость постройки, т.е. для примера 1, у нас есть 2 варианта пути, самый выгодный 1:
1) 1 2 (2); 2 3 (1) - стоимость 2 время 4, в скобках номера предложений
2) 1 3(3) - стоимость 3 время 1
Но во 2 примере не сходится, я так понял что-то упускаю, но не понимаю что именно?
С этим понятно, а почему рассматривается в примере 2 путь 1 2 3, если там время 4, тоже максимальная берется? Ответ это самый длинный путь с минимизированной самой дорогой построенной предложенной линии?
Sunter, простите, ответил на коммент до редактирования. Там на самом деле неважно и только второе предложение и оба вместе дают одинаково хороший ответ, ведь второе предложение самое дорогое. Так что 1 2 тоже валидный ответ.
Sunter, Ну, время - путь в графе кратчайшей длины. В примере 2 добавив "1 3 1 3" вы создали путь из 1 в 3 длинной 3 (из одного нового ребра). Он укладывается в нужное ограничение.
Добавление ребра "2 3 2 1" не помагает, потому что оно участвует в пути 1-2-3, и его стоимость 2+2 = 4, не укладывается в лимит по времени. Но добавить его в ответ все-равно можно, потому что цена добавления 1 меньше цены первого добавления. И кратчайший путь в графе (где длины ребер - время) все еще остается 3, через одно новое ребро 1-3.
Wataru, Можете пожалуйста придумать еще один тест чтобы все было ясно, проста как я понимаю нам надо построить пути такие что, чтобы мы использовали дороги стоимостью « min и меньше чем min» чтобы P требование были удовлетворены?
Смотрите: вы добавляете в граф какие-то ребра. Надо чтобы после этого кратчайшие пути между заданными парами вершин укладывались в заданные ограничения. Ведь добавляя ребра вы можете какие-то пути улучшить (какие-то может и не улучшатся от каких-то ребер, но хуже нигде не станет. Ведь никто не заставляет пакеты ходить по новым ребрам).
Среди всех вариантов добавить ребра и уложиться в ограничения вам надо выбрать тот, который использует наименнее дорогие добавления. Не суммарно, а худшее.
