大家好。这里有一个问题：X 国有 n 个城市，它们被分配了从 1 到 n 的数字。该国的首都编号为 n。铁路铺设在城市之间。
但是，根据画布的宽度，道路可以分为两种类型。任何火车只能在一种轨道上行驶。传统上，一种道路标记为R，另一种道路标记为B。也就是说，如果从一个城市到另一个城市的路线同时具有R类道路和B类道路，则没有火车能够沿着该路线通过。从一个城市到另一个城市，您只能在仅由 R 类道路或 B 类道路组成的路线上行驶。
但这还不是全部。在 X 国的道路上，您只能从编号较低的城市移动到编号较高的城市。这解释了居民大量涌入首都的原因，首都的数量为 n。
如果没有一对城市 A 和 B 使得从 A 到 B 可以通过类型 R 的道路和类型 B 的道路到达，则铁路地图被称为最优。换句话说，对于任何一对城市，它是确实，从数量较少的城市到数量较多的城市，只能通过一种类型的道路到达，或者根本无法建造路线。看看给你的卡是否是最佳的。
那么，那么这些R和B路就设置好了。我正面解决了，也就是我傻傻的找到了从顶点1到N的所有路径，发现那里只有一种路。但是已经在 25 个城市中，一切都运行得非常长。我知道有一些更简单的算法，但没有想到。给我一些想法，以哪种方式思考？