@Sunter

Как устроен вывод в задаче?

Условие задачи:
Сеть провайдеров состоит из 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

Пример 1
ввод
3 0
3
2 3 2 1
1 2 2 1
1 3 1 3
1
1 3 4
вывод
2
1 2

Пример 2
ввод
3 1
1 2 2
2
1 3 1 3
2 3 2 1
1
1 3 3
вывод
2
1 2

Не понятно с примером 2. Я думал, что необходимо найти минимальную стоимость постройки, т.е. для примера 1, у нас есть 2 варианта пути, самый выгодный 1:
1) 1 2 (2); 2 3 (1) - стоимость 2 время 4, в скобках номера предложений
2) 1 3(3) - стоимость 3 время 1
Но во 2 примере не сходится, я так понял что-то упускаю, но не понимаю что именно?
  • Вопрос задан
  • 267 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Минимизируйте стоимость строительства самой дорогой построенной предложенной линии.


не сумма всех взятых ребер, а стоимость максимального из них.

1 2 (2) и 2 3 (1) - максимальная стоимость 2 (max(1,2)).

1 3 (3) - максимальная стоимость 3 max(3). 3 больше 2, значит ответ выше лучше.

Так задача легче, чем с суммой.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы