我在一个编码站点遇到这个问题，我不知道如何解决它。这篇社论没有发表，我也无法在网上找到任何相关文章。所以我在这里问这个。
问题：
有一个包含n个顶点和m条边的图g。顶点从1到n进行编号。每个节点也被着色为黑色或白色。您需要计算从1到n的最短路径，以便黑白节点的差异最多为1。
很明显，直接应用dijkstra算法是行不通的。如有任何帮助，我们将不胜感激。谢谢您！
最佳答案
我们可以考虑一个修改过的图并在这个图上运行dijkstra：
对于原始图中的每个节点，修改后的图将有多个元顶点（理论上，无穷多个），每个元顶点对应不同的黑白差分。在使用dijkstra探索图形时，只需要创建节点。因此，您不需要无限多的节点。
边缘很简单（您也可以在探索时创建它们）。如果当前位于黑白差异d的节点，并且原始图形有一条到白色节点的边，则可以创建到黑白差异d-1的相应节点的边。如果原始图形有一条到黑色节点的边，则在修改后的图形中创建一条到相应节点的边，且黑白差d+1。您不必将它们视为不同的节点。也可以将dijkstra变量存储在按黑白差分组的节点中。
以这种方式运行dijkstra将为您提供到任何黑白差异节点的最短路径。一旦到达具有可接受的黑白差分的目标节点，就完成了。