Задача:
Найти кратчайший путь между двумя городами.Города связаны дорогами с односторонним движением. Города находятся в файле .txt следующим образом:
// От // // До // // Расстояние //
Например:
Лондон Глазго 180
Манчестер Ливерпуль 80
Йорк Кембридж 415
Йорк Манчестер 260
Глазго Йорк 315
Глазго Манчестер 315
По заданному городу-источнику S и целевому городу T найдите кратчайший путь.Рассчитайте расстояние и получите выбранный путь.
Проблема: Мне вообще не разрешается использовать какой-либо контейнер STL.Невозможно использовать контейнеры, такие как std :: list, std :: vector, std :: pair, std :: set и т. Д. Однако я могу использовать свои собственные реализованные динамические структуры данных.
I 'Я не знаю, какие структуры данных мне следует реализовать и как их реализовать.Кроме того, я должен использовать приоритетную очередь, или кучу, или что-то еще?Также интересует список смежности или матрица смежности.
Мне все равно, хорошо ли оптимизировано решение или нет.
Я много гуглял, но все реализации алгоритмов Dijkstras, которые я обнаружил, используют множество контейнеров STL, которые мне не разрешено использовать.
Любые советы, подсказки или ссылки приветствуются.Спасибо.