Как решить олимпиадную задачу с графами?

Есть граф. Нужно найти кратчайший путь из точки A в конец.
В некоторых вершинах графа есть награды, которые нужно собрать кратчайшим способом.
Какой алгоритм лучше применить и как?
Полное условие:
Городок Еловый славится своими двумя вещами — здесь каждую неделю Новый год и везде очень узкие дороги. Если с первым еще можно как-то бороться, то со вторым городу очень тяжело. Именно поэтому жителям нужна Ваша помощь!

Вам дана карта города Еловый. Как ни странно, он очень похож по форме на елку. Елью в данной задаче будем называть неориентированный граф, состоящий из цикла, к которому присоединён черенок, представляющий собой несколько последовательно связанных рёбер. Самую отдалённую от цикла вершину черенка будем называть корнем ели. В корне находится выезд из города. На некоторых улицах города с последнего Нового года лежат ёлки, которые надо вывезти из города.

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

Елки ждут!
  • Вопрос задан
  • 102 просмотра
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Поскольку тут очень специфический граф - тут не надо никаких алгоритмов для графов. Это задача тупо на разбор случаев. Единственные возможные маршруты в этом графе - начать с какой-то вершины цикла и поехать вправо или влево, пока не доедете до черенка, и дальше по нему к выезду. Или можно начать на черенке и уехать. Очевидно, что первые два варианта - это надо начать с ближайшей к черенку елки в каждую сторону и поехать в ту же сторону дальше. Длина маршрута - количестов ребер минус рассотяние от елки до черенка в данную сторону. Третий путь можно начать на ближайшей к циклу елке на черенке и ехать на выход. Первые 2 варианта - если есть елки на цикле, третий вариант - если нет.

Вам надо только понять какие вершины в цикле, а какие на черенке. Тут можно обходом в глубину или ширину это найти. Или даже тупо циклом. В графе есть одна вершина степени 1 - она же выезд. От нее надо идти к соседним, пока не дойдете до единственной вершины степени 3. Пройденные так вершины будут черенком. Остальные - в цикле.

А дальше вам надо посчитать длины трех маршрутов и выбрать из них лучший.
Ответ написан
Комментировать
YaKotikTvoy
@YaKotikTvoy
Стьюдик
Здесь вам нужно найти остовное дерево графа, да притом такое, что его можно выпрямить. Но так как, там по сути, как я понял, просто цикл, а ещё есть одно тупиковое ответвление, то вам просто нужно взять и запустить DFS, либо BFS алгоритм с точки, которая около черенка.
Для того, чтобы BFS или DFS сразу не пошли к черенку, удалите ребро ведущую к выходу, то есть тупику, но при этом подразумеваете, что оно есть , это уже и будет то минимальное расстояние, остовное дерево.
Запишите этот путь в массив или множество и задача решена.
6282ce27c8710274314724.png
Вот DFS, припишите то, что нужно для записи пути и выведите его.
N,M = [int(i) for i in input().split()]
G = {}
for i in V:
    if i not in used:
            t += 1
            dfs(i,G,used)

N, M - количество вершин и ребер соответственно.
Все ребра и вершины необходимо прописать самому.
В данном случае, лучше DFS (поиск в глубину).
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы