На эту неделю подготовили простой тренировочный контест по алгоритму Дейкстры.

Эта подборка привязана к теории про поиск кратчайших путей во взвешенном графе без отрицательных рёбер. Здесь можно спокойно потренировать базовую реализацию Дейкстры, работу с priority_queue, массивом расстояний, восстановлением маршрута и разными моделями задач, где «стоимость пути» может означать время, цену, риск, количество пересадок или другой параметр.

Теория:

• 13.2 Алгоритм Дейкстры — https://olprog.ru/articles/olprog/graphs/shortest-paths/dijkstra/

В контест вошли задачи:

• Кратчайший путь в городе — https://judje.olprog.ru/problem/cityshortestpath
• Расстояния от штаба — https://judje.olprog.ru/problem/distancesfromhq
• Успеть на поезд — https://judje.olprog.ru/problem/catchthetrain
• Маршрут экспедиции — https://judje.olprog.ru/problem/expeditionroute
• Робот на складе — https://judje.olprog.ru/problem/warehouserobot
• Самый безопасный путь — https://judje.olprog.ru/problem/safestpath
• Ближайший склад — https://judje.olprog.ru/problem/nearestwarehouse
• Остановка в столице — https://judje.olprog.ru/problem/capitalstopover
• Пешком или автобусом — https://judje.olprog.ru/problem/walkorbus
• Купоны на скидку — https://judje.olprog.ru/problem/discountcoupons
• Надёжный маршрут — https://judje.olprog.ru/problem/reliableroute
• Цифровые превращения — https://judje.olprog.ru/problem/digittransforms
• Путь с пересадками — https://judje.olprog.ru/problem/pathwithtransfers
• Режимы движения — https://judje.olprog.ru/problem/travelmodes
• Путь с заправками — https://judje.olprog.ru/problem/refuelpath
• Расписание паромов — https://judje.olprog.ru/problem/ferryschedule

Этот контест подойдёт тем, кто хочет:

• закрепить классическую Дейкстру на взвешенных графах;
• научиться аккуратно хранить расстояния и не забывать про long long;
• потренироваться отличать обычный BFS от задачи, где уже нужны веса рёбер;
• увидеть, как одна и та же идея работает в задачах про дороги, доставку, транспорт, расписания и состояния;
• подготовиться к более сложным темам на кратчайшие пути.

Рекомендуем идти так: сначала прочитать теорию, затем решить первые задачи на базовую Дейкстру, а после этого переходить к задачам, где появляются дополнительные состояния: купоны, пересадки, режимы движения, заправки или расписания. Именно такие задачи хорошо показывают, что вершиной графа может быть не только город или клетка, но и состояние вида «где мы находимся и что уже использовали».

Во время решения полезно каждый раз отдельно проговаривать:

• что является вершинами графа;
• что является рёбрами;
• какой параметр мы минимизируем;
• все ли веса неотрицательные;
• нужно ли добавлять дополнительные состояния;
• какой INF безопасно выбрать для расстояний.

Удачи в решении!

Ждём ваши результаты, вопросы и впечатления от задач.