c++ - 在 3 个字符串 vector 中查找连接

Question

我用 C++ 编写了一些代码，用于查找通过公路或航类连接的两个城市之间的最短路径。城市可以与直飞航类或间接航类相连。用户可以这样输入航类:

AAA AAG 300
AAA AAB 1
AAA AAG 298
AAB AAC 1
AAB AAG 297
AAC AAD 1
AAC AAG 296
AAD AAE 1
AAD AAG 295
AAE AAF 1
AAE AAG 294
AAF AAG 1

第一个字符串是离开城市，第二个是目的地，数字是飞行时间。我将这些值存储在 3 个 vector 中:

   vector<string> leavingCities;
   vector<string> destCities;
   vector<int> flightTimes;

我很难在这些 vector 中找到间接航类 - 我的意思是有时从 AAA 到 AAG 的直接飞行时间比通过 AAB、AAC、AAD、AAE 和 AAF 的间接飞行时间长得多，然后我必须选择更短的路线和存储我旅行过的城市。有没有找到最短时间和路线的解决方案？航类列表可能会有所不同，并不一定要像这样。也许有一些更好的容器来存储这样的数据？请帮帮我。

Answer 1

您确实应该将您的问题分解为理解如何您将如何解决它，然后进入代码。如果您不了解如何解决它，通常只编写代码是无济于事的。

首先，您的问题可以归类为在图算法中寻找最短路径。维基百科有一整页关于它们，但是 Dijkstra's算法可能是最适合您的。

了解了方法后，您就可以着手实现了。如果你可以使用它们，那里有很多不错的图形库，例如 Boost.Graph ，但我怀疑作为一项任务，您将被要求从头开始自己实现它。但是，我不建议没有经验的程序员查看 Boost 源代码 - 它们非常可怕，尽管一旦您有了更多经验，这是一种很好的学习方式。

祝你好运