We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
fromcollectionsimportdeque,defaultdictEDGE_WEIGHT=6defbfs(n:int,m:int,edges:list[list[int]],s:int)->list[int]:dist=[float('inf')]*(n+1)dist[s]=0# graph = {1: [2, 3], 2: [1], 3: [1, 4], 4: [3]}graph=defaultdict(list)fornodeA,nodeBinedges:graph[nodeA].append(nodeB)graph[nodeB].append(nodeA)# use deque for BFSqueue=deque([s])# use set() for O(1) hashtable lookupvisited=set([s])whilequeue:currNode=queue.popleft()forneighbouringraph[currNode]:ifneighbournotinvisited:visited.add(neighbour)queue.append(neighbour)# update distance if the new one is shorterifdist[currNode]+EDGE_WEIGHT<dist[neighbour]:dist[neighbour]=dist[currNode]+EDGE_WEIGHTres=[-1ifx==float('inf')elsexforxindist]returnres[1:s]+res[s+1:]
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Breadth First Search: Shortest Reach
You are viewing a single comment's thread. Return to all comments →
Python3 solution, what do you guys think?