- 已关闭**。此问题需要details or clarity。当前不接受答案。
- 想要改进此问题？**添加详细信息并通过editing this post阐明问题。
2天前关闭。
这篇文章是编辑和提交审查2天前。
Improve this question
我正在尝试解决LeetCode问题1129. Shortest Path with Alternating Colors：
给定一个整数n，它是有向图中的节点数，图中的节点标记为0到n - 1，每条边都是红色或蓝色的，可能有自边和平行边。
您将获得两个数组redEdges和blueEdges，其中：redEdges[i] = [aᵢ, bᵢ]指示在图中存在从节点aᵢ到节点bᵢ的有向红边，并且blueEdges[j] = [uⱼ, vⱼ]指示在图中存在从节点uⱼ到节点vⱼ的有向蓝边。
返回一个长度为n的数组answer，其中每个answer[x]是从节点0到节点x的最短路径的长度，使得边缘颜色沿着路径交替，或者-1，如果这样的路径不存在。
示例1：
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]下面是我解决这个问题的代码：
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
res = [0] + [-1]*(n-1)
Red = defaultdict(list)
Blue = defaultdict(list)
for x,y in redEdges:
if x!=0 or y!=0:
Red[x].append(y)
for x,y in blueEdges:
if x!=0 or y!=0:
Blue[x].append(y)
def dfs(vertex,color,cost):
if color == "red":
for x in Red[vertex]:
if res[x] != -1:
res[x] = min(cost,res[x])
else:
res[x] = cost
if vertex in Red.keys():
del Red[vertex]
dfs(x,"blue",cost+1)
else:
for x in Blue[vertex]:
if res[x] != -1:
res[x] = min(cost,res[x])
else:
res[x] = cost
if vertex in Blue.keys():
del Blue[vertex]
dfs(x,"red",cost+1)
dfs(0,"red",1)
dfs(0,"blue",1)
return res但对于以下输入：
redEdges=[[2,2],[0,1],[0,3],[0,0],[0,4],[2,1],[2,0],[1,4],[3,4]]
blueEdges=[[1,3],[0,0],[0,3],[4,2],[1,0]]...我的输出是：
[0,1,4,1,1]但正确的解决办法是：
[0,1,2,1,1]...因为存在从节点0到节点2的路径，如下所示：
red blue
0 -----> 4 -----> 2我不知道为什么我的代码没有给出2，因为这个路径应该通过我的DFS算法找到。
我认为它可能是[0，0]边的东西，但它似乎对解决方案没有影响。
我的代码有什么问题？
1条答案
按热度按时间ccrfmcuu1#
问题是你的代码删除了它访问过的顶点，但是在回溯时没有恢复它，有可能从顶点0到你刚刚删除的顶点还有另一条路径需要遍历，而且是一条更短的路径。
下面是演示该问题的示例输入：
您的代码将正确创建以下邻接列表：
使用
dfs，路径0，1，2，3，4将被访问，并且在此遍历期间，这些字典中的所有键将被删除。由于从0开始的输出边上的循环仍然有效，dfs将仍然沿着从0到3的红色边。但是在那里它找不到蓝边，因为关键字3已经不在那里了，所以算法找不到从0到4的更短路径，也就是0，3，4这不是你的问题，但是BFS更适合于寻找最短路径。我建议你修改算法，用BFS代替。
为了得到一个完整的答案，这里有一个使用BFS的扰流板解决方案：
class Solution: def shortestAlternatingPaths(self, n, redEdges, blueEdges): # Build a separate adjacency list for each color adj = [[[] for _ in range(n)], [[] for _ in range(n)]] for i, edges in enumerate((redEdges, blueEdges)): for x, y in edges: if x or y: adj[i][x].append(y) # Collect shortest distances for each color separately res = [[0] + [-1] * (n-1), [0] + [-1] * (n-1)] # Start BFS at node 0, traversing with either color frontier = [(0, 0), (0, 1)] distance = 1 while frontier: # BFS loop nextfrontier = [] for node, color in frontier: for neighbor in adj[color][node]: # If not yet visited with this color... if res[color][neighbor] == -1: res[color][neighbor] = distance nextfrontier.append((neighbor, 1-color)) frontier = nextfrontier distance += 1 # Get the minimum distance per node from the two color alternatives return [min(a, b) if min(a, b) > -1 else max(a, b) for a, b in zip(*res)]