|
Бизнес-проект
(Время: 5 сек. Память: 256 Мб Сложность: 99%)
На уроке технологии ученикам дали задание составить Бизнес-проект. Алексей давно подумывал открыть компанию по доставке грузов, поэтому решил написать программу, которая поможет составлять план доставки грузов и минимизирует расходы. Все свои накопления Алексей вложил в этот проект. Для начала был приобретён один грузовой автомобиль грузоподъёмностью W.
Есть N клиентов. Необходимо развести K товаров, каждый из которых имеет вес wi. Все товары хранятся на базе. Также нам дана матрица dist расстояний между пунктами (база имеет номер 0, клиенты – номера от 1 до N; dist[i, i] = 0; dist[i, j] = dist[j, i]). Так как товаров может быть много, и за один раз автомобиль может увести товары суммарной массой не больше W, то автомобиль вынужден делать несколько рейсов, возвращаясь каждый раз на базу. Рейс начинается и заканчивается на базе. Масса любого груза меньше W.
Считается, что ваша программа успешно проходит тест, если она выдаёт ответ не хуже, чем план развоза Алексея на том же наборе входных данных, который минимизирует пройденное автомобилем расстояние.
Входные данные
В первой строке входного файла INPUT.TXT записаны три натуральных числа N, K, W (1 ≤ N ≤ 100; 1 ≤ K ≤ 300; W ≤ 5000). В следующих строках дана квадратная матрица расстояний размером (N + 1)2 . Далее в K строках дана информация о товарах: масса текущего товара и номер клиента (число от 1 до N). Все массы и расстояния на вводе – натуральные числа не больше 300.
Выходные данные
В выходной файл OUTPUT.TXT в первой строке выведите число рейсов, которое нужно совершить. Далее должны следовать блоки информации о рейсах (одному рейсу соответствует один блок). Блок состоит из четырёх строк: в первой приведены через пробел номера доставляемых за данный рейс товаров в произвольном порядке (номера лежат в пределах от 1 до K), во второй – загрузка автомобиля (суммарная масса доставляемых товаров), в третьей – маршрут (номера пунктов через пробел в порядке объезда), в четвёртой – пройденное расстояние за рейс. В последней строке выведите суммарное пройденное расстояние за все рейсы. Разделяйте числа в строке ровно одним пробелом, блоки отделяйте друг от друга, а также от первой и последней строк пустыми строками, как показано в первом тесте.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 8 732
0 84 32 45 78
84 0 55 43 94
32 55 0 13 84
45 43 13 0 89
78 94 84 89 0
101 1
116 1
292 4
94 3
89 2
163 4
80 3
126 1
| 2
7 4 1 2 8 5
606
0 2 3 1 0
172
3 6
455
0 4 0
156
328
|
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
