我遇到了问题 Breadth First Search: Shortest Reach在 Hackerrank 中,这是我在 python 中的解决方案。但是我的代码只通过了 7 个测试用例中的一个。我在这个实现中哪里错了?
#Hackerrank
#Topic : Graphs
#Url : https://www.hackerrank.com/challenges/bfsshortreach/problem
def bfs(i, n, E):
level = [-1] * (n+1)
queue = []
level[i] = 0
queue.append(i)
while len(queue) > 0:
head = queue[0]
queue = queue[1:]
for j,k in E:
if j == head:
if level[k] == -1:
level[k] = 1 + level[j]
queue.append(k)
return level
q = int(input())
for case in range(q):
e = input().split(" ")
n = int(e[0])
m = int(e[1])
E = []
for edge in range(m):
e = input().split(" ")
u = int(e[0])
v = int(e[1])
E.append([u,v])
s = int(input())
distance = bfs(s, n, E)
dist = []
for i in distance[1:]:
if i > 0:
dist.append(str(i*6))
if i < 0:
dist.append(str(-1))
print(" ".join(dist))
print("")
最佳答案
问题表明该图是无向的,但您仅通过添加 1 条边使其有向:
E.append([u,v])
你还应该添加反方向的边
E.append([v,u])
关于python-3.x - 广度优先搜索 : Shortest Path using Python,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51389802/