Wataru

В сетевом роутинге, в основном, нет* центрального узла с информацией о всей топологии, чтобы искать пути. Так что там вообще не работает Дейкстра, а работают распределенные алгоритмы.

А так, да, на очень специфичных гарфах всеядный алгоритм Дейкстры не самый лучший вариант. И ваш алгоритм тут получается быстрее.

* Вообще, есть такая тема, как Software Defined Networking, где как раз есть центральный узел, который все и решает, но это чисто теория пока, и там суть не в поиске кратчайших путей в графе а во всяких сложных механизмах приоритезации трафика и устойчивости к сбоям.

Можно целочисленным линейным программированием решать. Бинплиском перебтрайте ответ (k), потом составляйте задачу, где у вас переменные: сколько монет каждого типа берём в каждый из k разменов. И еще будут неравенства, что каждый тип монет используется суммарно не больше, чем есть монет. Целевая функция - любая.

Еще можно чуть по-другому: находите переблром все варианты одного размена. Потом у вас переменные будут, сколько раз каждый из вариантов берете. Ограничения на общий расход каждой монеты, а целевая функция - сумма переменных. Тут нет бинплиска, но тоже ЦЛП.

Вообще, преобразование из double в int - это не ошибка. Это warning (и то, он выводится, только если компилятору указать -Wconversion. Код выше этот варнинг выдает во втором месте, но все-равно компилируется.

Если у вас преобразование умышленное, и вы знаете, что там не будет ошибки переоплнения, то вы можете использовать static_cast тогда компилятор не будет выдавать предупреждение.

Вам надо в вашем алгоритме еще завести словарь, куда вы для каждой вершины будете складывать предыдущую в пути. Там, где вы соседнюю вершину кладете в очередь - там надо сарзу смотреть, посещенная она или нет и класть только если нет. Вот в этот момент вы знаете, что вы пришли в graph[city][i] из city.

В конце циклом по этому массиву пердыдущих вершин пройдитесь и так получите путь в обратном порядке.

Ну нет его в стандартной библиотеке, как и длинных чисел. Используйте gmplib, например.

Потому что это 2 разных графика, 2 разных примера. Могли бы на втором обозвать вместо f и g f` и g`. Но авторам, наверно, было лень.

Для такой вот работы идеально подходят связные списки. Там можно менять объект не портя никакие итераторы. Проблема только в том, что связные списки в питоне не реализованы на уровне языка. Поищите реализацию, наверняка есть удобный модуль со списками.

Еще можноиспользовать обычный list, только вы итерируйтесь циклом while и используйте индексы:

i = 0
while i < len(arr):
  x = arr[i]
  j = i+1
  while j < len(arr):
    if ShouldDelete(arr[j], arr[i]):
      del a[j]

Это будет в n раз медленнее, к сожалению. Можно наверно слайсами сделать быстрее:

arr[i+1:] = y for y in arr[i+1:] if not ShouldDelete(x, arr[i])

Я не питонист и возможно ошибку допустил. И мне этот код не кажктся очень понятным, но возможно это истиный путь для питона.

А так, в общем случае, идет двойная итерация с пометками элементов на удаление.

Какого-то названия этот прием не имеет, ибо это костыль для конкретных реализаций контейнеров.

Теоретически - да. Специализированный движок лишь для вашей игры будет быстрее и легче многофункционального комбайна UE. На практике у вас там объем работы будет на сотню человеко-лет.

Подсказка: вот то число, что у вас в конце выводится - это 2^64-1. Еще подсказка: size_t на современных платформах имеет размер 64 бита.

У вас переполнение. Вы там из 0 вычитаете 1 в итерации цикла, получаете самое большое число, представимое в 64-битном типе.

Надо переписать цикл на while и делать из него break по достижению 0. Или тип переменной сменить на знаковый.

Занумеруйте все биты от 0 до 16. Потом транспонируйте эту матрицу. Потом посмотрите на разность результата и конца. Вот эти вот числа - это на сколько бит надо сдвинуть исходные биты, чтобы они встали на нужное место.

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

0 4 8 12
1 5 9 13
2 6 10 13
3 7 11 15

0 -3 -6 -9
3 0 -3 -6
...

Все биты с одинаковым смещением можно подсчитать за 3 операции: Сдвиг, битовая маска и побитовое или в ответ.
Я тут вижу 7 разных чисел -9,-6,-3,0,3,6,9.
Например, для 0 и 3 у вас будет

answer = (source & 0x1248) | ((source << 3) | 0x2480) | ...

Это не 8 пока еще операций, а аж 20. Возможно можно как-то еще их сгруппировать.

Edit: Возможно, еще подход с таблицей будет быстрее. Для каждого из 16 возможных значений строк выдавайте битовое число - столбец, где эти 4 бита на позициях 0, 4, 8,12. Тогда ответ будет table[source&0xf0] | (table[(source>>4)&0xf] << 1) | (table[(source>>8)&0xf] << 2) | (table[(source>>12)&0xf] << 3).

Тут 13 битовых операций и 4 чтения из памяти.

Часть задач там платные, без подписки даже условие не прочитать.
Случайный выбор задачи не проверяет, бесплатная ли она, и может перекинуть вас на премиум-задачу.

Edit: ах да, они этот список еще меняют иногда. Так что вполне возможно, что вы эту задачу когда-то раньше уже даже решили, но теперь она стала платной.

Вам нужна lock-free хеш таблица (гуглите Lock free unordered_map). В стандартной библиотеке таких структур нет. Или просто используйте свои мьютексы при каждом обращении к структуре.

iostream - лишь обертка над системными вызовами. Входной и выходной потоки - это концепция системы.

Это целый набор шаблонных классов, которые переопределяют операции побитового сдвига, поэтому у вас в программе используются << и >>. Под капотом это все доходит до системных вызовов, которые пишут или читают данные в системные потоки (pipe). Там тупо команды "запиши вот эти байты" и "отдай мне вот в этот буфер максимум столько-то байт".

Система, насколько я знаю, для каждого pipe'а поддерживает какой-нибудь кольцевой буфер в который процессы могут писать и читать оттуда, через системные вызовы выше.

При работе с клавиатурой, дайвер клаиватуры получает команды от устройства. Операционная система, зная какое окно сейчас активно, посылает эти команды в поток для нужного окна.
При работе с сетью, дайвер сетевого устройства получает пакеты, обрабатывает их, передает операционке, она определяет, в какой поток надо эти данные записать, и записывает туда.

ОС-ка поддерживает список потоков, которые ждут чтения из каждого буфера. Когда что-то в буфер записывается, эти потоки просыпаются.

Чтобы модифицировать поведение. Вы передаете в качестве параметра - что делать. Вместо того, чтобы писать отдельно несколько функций, отличающихся лишь маленькой частью, вы пишите лишь одну функцию, где эта маленькая различная часть - вынесена в передаваемую функцию.

Иногда вообще по-другому не сделать. Например, очередь задач. Вот надо вам чтобы в одном потоке выполнялась куча маленьких функций. Тут единственный сопособ - это функцию сохранить в переменную, засунуть в какую-то очередь и потом, когда станет нечего делать, достать ее оттуда и выполнить.

Или у вас вопрос, почему указатель? Ну ведь фунция - это огромный кусок кода в памяти. Логично же ее передавать как указатель, как и массивы, например. Но тут есть еще и низкоуровневая проблема - в процессоре есть защита от исполнения данных. Без дополнительных танцев с бубном, вы никак данные не выполните, даже если там записан корректный машинный код. Поэтому все функции записаны в read-only секции памяти, специально помеченной, как разрешенная к исполнению. Поэтому единственный сопособ как-то эти данные куда-то передать - это указатель туда. Сами данные-то не перемещаемые.