Я решил
попробовать эту
задачу, но с самой задачи не стыковка по условию, я не могу понять логику расчета
Решать не надо, просто пнуть в сторону - что я не так понял
Я решил обойти граф и на каждой ветке я считал стоимость как
cost = (s > 28 ? 28 : s) * l
Но результат не совпадает с результатом условия, вручную я просчитал графы - и вижу что в задании входные данные не соответствуют выходным. Или я не понял как считать граф.
Яндекс готовится к запуску системы доставки товаров Яндекс.Маркета с помощью дронов. По текущему законодательству, автоматизированные дроны должны перемещаться только по заранее заданным воздушным трассам.
Нужно написать маршрутный модуль, который по схеме трассы (направленный ацикличный граф — DAG) возвращает все варианты маршрутов, отсортированные от самого быстрого, до самого длительного. В схеме каждый следующий участок приближает к точке назначения, нельзя вернуться назад и нет тупиков — каждый путь приводит к месту назначения.
Трасса состоит из пересечений/перекрестков и участков трассы между этими пересечениями. Каждый участок трассы имеет разную длину (в метрах) и максимальную скорость (в м/с), разрешенную на этом участке. Дрон так же имеет максимальную скорость (28 м/с), быстрее которой лететь не способен.
Маршрутный модуль должен возвращать функцию, которая принимает два параметра:
function findAllRoutes(segments, finishId) {
...
}
module.exports = findAllRoutes;
Пример входных данных:
const segments = [
{
f: ’1’, // from: id исходного узла
t: ’2’, // to: id конечного узла
l: 200, // length: длина отрезка
s: 30 // speed: ограничение скорости на участке
},
{f: ’2’, t: ’3’, l: 150, s: 30},
{f: ’2’, t: ’4’, l: 200, s: 25},
{f: ’2’, t: ’5’, l: 250, s: 30},
{f: ’3’, t: ’6’, l: 100, s: 25},
{f: ’4’, t: ’6’, l: 75, s: 15},
{f: ’5’, t: ’6’, l: 50, s: 20},
];
const finishId = ’6’;
const result = findAllRoutes(segments, finishId);
Пример выходных данных:
[["1","2","3","6"],["1","2","5","6"],["1","2","4","6"]]
Мой расчет[
{
f: '1', // from: id исходного узла
t: '2', // to: id конечного узла
l: 200, // length: длина отрезка
s: 30 // speed: ограничение скорости на участке
}, 200 * 28 = 5600
{f: '2', t: '3', l: 150, s: 30}, 150 * 28 = 4200
{f: '2', t: '4', l: 200, s: 25}, 200 * 25 = 5000
{f: '2', t: '5', l: 250, s: 30}, 250 * 28 = 7000
{f: '3', t: '6', l: 100, s: 25}, 100 * 25 = 2500
{f: '4', t: '6', l: 75, s: 15}, 75 * 15 = 1125
{f: '5', t: '6', l: 50, s: 20}, 50 * 20 = 1000
];
[["1","2","3","6"],["1","2","5","6"],["1","2","4","6"]]
[[5600 + 4200 + 2500 ], [5600 + 7000 + 1000], [5600 + 5000 + 1125]]
[12300, 13600, 11725]
насколько я понимаю должно быть так [["1","2","4","6"], ["1","2","3","6"], ["1","2","5","6"]]