teknik2008
@teknik2008
Расскажите про GOLANG. Мне интересно

Не стыковка в вопросе на тестовое задание яндекс contest?

Я решил попробовать эту задачу, но с самой задачи не стыковка по условию, я не могу понять логику расчета
Решать не надо, просто пнуть в сторону - что я не так понял
Я решил обойти граф и на каждой ветке я считал стоимость как 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"]]

  • Вопрос задан
  • 131 просмотр
Решения вопроса 1
lastuniverse
@lastuniverse
Всегда вокруг да около IT тем
cost = l / (s > 28 ? 28 : s)
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
01 мая 2024, в 02:11
5000 руб./за проект
01 мая 2024, в 00:29
2000 руб./за проект
01 мая 2024, в 00:20
15000 руб./за проект