You are viewing a single comment's thread. Return to all comments →
C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star:) )
std::vector<int> bfs( int const nodesCount, int const edgesCount, std::vector<std::vector<int>> const & edges, int const nodeStart ){ using namespace std; static constexpr auto edgeCost{6}; static constexpr auto startNodePathCost{0}; static constexpr auto isolatedNodePathCost{-1}; auto nodeToNeighbours{vector<vector<size_t>>(nodesCount + 1, vector<size_t>{})}; for(auto const & edge: edges){ nodeToNeighbours.at(edge.at(0)).emplace_back(edge.at(1)); nodeToNeighbours.at(edge.at(1)).emplace_back(edge.at(0)); } auto qNodes{queue<size_t>{}}; qNodes.push(nodeStart); auto pathesShortest{vector<int>(nodesCount + 1, -1)}; pathesShortest.at(nodeStart) = startNodePathCost; auto nodeCurrent{numeric_limits<size_t>::max()}; auto pathCostNext{numeric_limits<size_t>::max()}; while(!qNodes.empty()){ nodeCurrent = qNodes.front(); pathCostNext = pathesShortest.at(nodeCurrent) + edgeCost; qNodes.pop(); for(auto const & nodeNext: nodeToNeighbours.at(nodeCurrent)){ if(pathesShortest.at(nodeNext) != isolatedNodePathCost){ continue; } qNodes.push(nodeNext); pathesShortest.at(nodeNext) = pathCostNext; } } pathesShortest.erase(begin(pathesShortest) + nodeStart); pathesShortest.erase(begin(pathesShortest)); return pathesShortest; }
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 →
C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star:) )