#algorithm #graph #path #graph-algorithm
#алгоритм #График #путь #граф-алгоритм
Вопрос:
это описание моей задачи, которое я переписал из своего задания.
Вы шпион со свежеприобретенной информацией, которая может привести к победе в продолжающейся войне. Вы должны вернуться в город, где находится ваша штаб-квартира. Вы можете путешествовать между городами по известным дорогам, но некоторые города находятся в состоянии войны, и вы гарантированно пострадаете там. У вас будет ограниченное время (количество городов, которые вы можете посетить), прежде чем вы истечете кровью — вам нужно добраться до больницы или до вашего штаба, где вас обработают — вы снова будете полностью здоровы. Теперь вам нужно найти путь (он не обязательно должен быть самым коротким!), Если он существует.
TLDR: найдите путь в невзвешенном двунаправленном графе между двумя узлами и выживите.
Ввод:
Number of cities
Number of cities at war, Number of cities with a hospital
Number of paths
Starting city ID, End (HQ's) city ID
Number of moves before you bleed out
[List of IDs of cities at war]
[List of IDs of cities with a hospital]
[List of paths [from to]]
Примеры:
In: (THIS ONE IS THE ONE I NEED HELP WITH)
6
1 1
5
0 5
2
2
3
4 5 1 2 2 3 0 1 2 4
Out:
0 1 2 3 2 4 5
In: (you'll get to the HQ before you die)
5
1 0
4
0 4
2
2
1 2 3 4 2 3 0 1
Out:
0 1 2 3 4
In: (here you'll bleed out)
5
1 0
4
0 4
1
2
1 2 3 4 2 3 0 1
Out:
No Path Found
Примечание: Графики не обязательно должны быть (и не являются) просто деревьями, это может быть любой график. Вам не обязательно начинать с города 0 (то же самое касается конечного города (штаб-квартиры)).
Я могу найти путь в любом графике, используя DFS или BFS by , даже эффективно для больших входных данных (100 тыс. городов, 500 тыс. путей), но я не могу вводить данные, подобные первому примеру, который я привел здесь (но не позже).
Входы, где я должен вернуться к уже посещенным узлам, — это то, что я не могу взломать. Разрешение повторного посещения уже посещенных узлов может (и приведет) к бесконечным циклам и другим проблемам. Я потратил целых 2 дня и просто не могу найти эффективное рабочее решение.
Я был бы очень рад, если бы вы могли подтолкнуть меня к правильному решению или дать мне подсказку, как это решить.
Спасибо.
Английский не мой родной язык, но я надеюсь, что все, что я написал, имеет какой-то смысл.