Нужно три архива с программами на Java. 2 и 3 архив — модификация 1го
Ниже ТЗ:
1 архив. Нахождение кратчайшего пути.
Ваша база данных — неориентированный граф без циклов без параллельных ребер, который имеет информацию о расстоянии (в км), времени (в часах) и стоимости (в рублях / кг) перевозки между двумя точками.
Этот граф хранится в файле russia.txt в следующем формате:
VertexA VertexB VertextC
VertextA VertexB dist:time:cost VertextC VertexB dist:time:cost
Например:
Москва Питер Барнаул
Москва Питер 120.0:4.3:100.50 Барнаул Питер 220.0:4.0:10.0
Имеется в виду, что между Москва и Питер 120,0 км, время поездки составляет 4,3 часа, а одна доставка 1 килограмма будет стоить 100,5 руб.
С помощью этого графа вы можете оценить время и стоимость доставки для ваших клиентов.
Вам предоставляется input.txt с запросами в каждой строке:
Москва Барнаул 10.0
Москва Питер 5.0
Имеется ввиду, что клиент собирается поставить 10 кг из Москва в Барнаул и 5 кг из Москва в Питер.
Ваша система должна оценить затраты времени и денег на запросы клиента, и поместить их в файл output.txt, в следующем виде:
Москва Барнаул 10,0 8,3 1105,0
Москва Питер 5,0 4,3 502,5
Первая строка означает "от Москва до Барнаул 10,0 кг будет доставлены в течение 8,3 часов (100,5 + 10,0) * 10,0 = 1105 рублей". Формулу расчета выводить в output.txt не нужно
Все числа должны быть записаны с помощью одного десятичного знака после запятой: 1234,5
2 архив.
Задача отличается от первой тем, что нужно минимизировать общую длину маршрутов для всего графа. Другими словами, вы решили сохранить лишь минимальное остовное дерево вашего графа с точки зрения расстояний.
Вход:
russia.txt
Москва Питер Барнаул
Москва Питер 120.0:4.3:100.50 Барнаул Питер 220.0:4.0:10.0 Барнаул Москва 1000.0:400.0:1000.0
input.txt
Москва Барнаул 10.0
Москва Питер 5.0
Выход:
output.txt
Москва Барнаул 10.0 8.3 1105.0
Москва Питер 5.0 4.3 502.5
3 архив.
Задача отличается следующим:
Готовясь к новогодним праздникам, вы знаете, что в последнюю неделю декабря будет пик на доставку. Босс дал вам задание, оценить, сможет ли компания преодолеть эту нагрузку. Таким образом, вас попросили оценить максимальный поток между парами городов.
Вы были в состоянии найти emperical правило, что пропускная способность дороги можно оценить следующим образом: емкость = 50 * длина / время (грузовики / час). Используйте эту информацию для оценки максимальной пропускной способности сети между городами.
Эмпирическим путем вы нашли, что пропускную способность дороги можно оценить следующим образом:
вместимость = 50 * расстояние / время
Используйте эту информацию для оценки максимальной пропускной способности между городами.
Вход:
russia.txt
Москва Питер Барнаул
Москва Питер 120.0:4.3:100.50 Барнаул Питер 220.0:4.0:10.0
input.txt
Москва Барнаул
Москва Питер
Ваша система должна оценить максимальный поток между городами, и записать его в файл выхода:
output.txt
Москва Барнаул 1395
Москва Питер 1395
Например. Первая строка означает "максимальный расход между Москва и Барнаул составляет 1395 грузовиков в час."
Поскольку поток = мин (50 * 120,0 / 4,3 = 1395, 50 * 220,0 / 4,0 = 2750) = 1395, т.е. выбираем меньшую из вместимостей
Все числа должны быть округлены до целых чисел. (integer)
Для всех задачек: Нужно использовать либо матрицу смежности или смежные списки для структуры данных.
Скорость алгоритма не оценивается.