tarp20, В вопросе у вас пока написано просто "в оптимальный сопосб". И никому, кроме вас непонятно, что значит - "оптимальный". Мне, например, большие коробки нравятся, потому что мой кот любит в них сидеть - поэтому любой оптимальный заказ должен содержать большую коробку. Но это мне, а что нужно в задаче - я не знаю.
Вы в сишный код передавайте массив дуг, который можно сделать тремя массивами (начало, конец и длина отдельно). А вектор векторов уже можете строить в сишном коде.
arktang, А еще V1 не подсчитать без сечегния на границы. Там, судя по рендеру, окончание - отрезок. А какой он длины? Как он расположен? V3 - нельзя подсчитать не зная под каким углом третье сечение к остальным двум. И расстояние L3 не понятно между какими точками меряется.
И пирамидой считать V2 нельзя. Только если продление сторон сойдется в точку, ибо в формуле вывода объема участвуют подобные фигуры и гарантируется, что площадь сечения посередине - среднее арифметическое сечений в концах.
А в вашем случае сечения вообще не полигонами будут - а кривыми.
Если вам нужна get_dists, то можете взять dijkstra и вернуть массив distances после цикла while. Остальной код не нужен.
Что бы 2 раза не гонять дейкстру для расстояний и пути можно вернуть одновременно массив distances и prev. Тогда по prev кодом в Dijsktra после while можно построить путь, если он нужен.
Ваш массив graph перобразуется в Graph в функции Load.
Это фактически и есть двумерый массив, но там ребра из каждой вершины сгруппированы в одну строчку.
Adamos, Как в вашем примере отсекается оптимальный вариант? Вариант "берем только первого продавца" - не отсекается, потому что он имеет минимум по всем товарам из всех взятых продавцов (он один).
Критерий не говорит, что какого-то продавца никогда не будет смысла брать потому что другие существуют. Он говорит, что не будет смысла брать его вместе с некоторыми другими.
Вот еще раз цитата:
Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару.
Adamos, Поэтому брать всех трех продавцов - невыгодно. Если какой-то продавец не дает минимум покакому-то товару, то все покупаемые у него товары можно купить у кого-то другого дешевле. Значит можно сделать так и выкинуть этого продавца и не платить ему за доставку.
Брать только перовго продавца или только двух других - локально оптимальные решения и их оба придется рассматривать в переборе.
Это лишь критерий оптимальности, достаточный, но не необходимый. Я предложил использовать его для отсечения в переборе.
Nurdaulet Turar, Можно ли в условии ставить несколько комманд? Вроде - если текущая клетка филоетовая - повернуть направо, шаг вперед, окрасить в оранжевый, вернуться в начало.
Magneto903, Зависит от графа. Дейкстра работает всегда более или менее одинаково. Этот алгоритм может работать в несколько раз быстрее или в сотни раз медленнее.
На сях, конечно, быстрее будет в среднем. Я бы советовал дейкстру в wasm скомпилировать, если вам так скорость нужна.
Magneto903,
О, я понял, почему этот алгоритм работает.
Это что-то типа волнового алгоритма и алгоритма Белла. Всякий раз как где-то ребро релаксируется, конец снова добавляется для рассмотрения.
Проблема с ним, что он может работать сильно дольше на неудачных тестах, потому что каждая вершина может быть в очереди сколько угодно раз. Тут вам повезло с графом, но может быть сииильно хуже.
Можно вообще сделать так, что длина очереди будет O(2^n) для n вершин. Но это будут весьма искусственные тесты. Может в вашем случае оно в среднем будет работать лучше.
Magneto903, Эта реализация пишет 0.034 в консоль. Видимо - это ms на прогон. Си-шная моя по прежнему 0.024ms. Весьма близко.
Но правильно ли работает? Я не понимаю, что там в get_path за алгоритм. Что-то среднее между BFS и дейкстрой. Проверьте, что путь такой же как прошлая версия выдает.
sazer, Судя по всему, там используется какая-то своя арифметика на целых числах на эллиптической кривой. Там вещественные числа вообще никаким боком привязаны быть не могут. Соответственно, вопрос точности не стоит - все числа-то целые. На С++ каком-нибудь был бы вопрос переполнения, но в питоне реализована длинная арифметика, поэтому и это не проблема.
А в чем здесь оптимизация? Разве что код короче, а работать будет даже медленнее, потому что на каждой итерации проверяет все значения, после текущего. У автора в вопросе же после первого большего элемента стоит break.
Василий Иванов, Она доказывается через разложение экспоненты в ряд тейлора и перегруппировку его в сумму двух рядов - синуса и косинуса. Запись на картинке - тупо применение формулы Эйлера, и никак не может использоваться в самом доказательстве.
Больше похоже на разбор свойств экспоненты от комплексных аргументов с применением формулы Эйлера.
