Войти Регистрация
Алгоритмы

87. Объезд всех ПВЗ за минимум минут

Сложная

Курьер Wildberries стартует со склада (точка 0) и должен заехать на каждый из остальных n - 1 пунктов выдачи ровно один раз. Возвращаться на склад не нужно.

minutes[i][j] — время в пути от точки i до j. Из-за односторонних улиц матрица может быть несимметричной. Верните минимальное суммарное время. Для n = 1 ответ 0.

В работе: Маршрутизация небольших развозов: 10–15 точек на курьера, когда точный ответ ещё считается.

Пример 1

Ввод
minutes = [[0, 4, 9], [4, 0, 3], [9, 3, 0]]
Вывод
7

0 → 1 → 2: 4 + 3 = 7.

Пример 2

Ввод
minutes = [[0]]
Вывод
0

Только склад.

Ограничения

  • 1 ≤ n ≤ 16
  • minutes[i][i] = 0, 1 ≤ minutes[i][j] ≤ 1000 при i ≠ j
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def courier_route(minutes):
ДП по подмножествамБитовые маскиЗадача коммивояжёрацельпо числу ответов

Источник: наша задача на данных Wildberries. Условие пересказано своими словами.