shahzaib1019
BAN USERHi. Are the shards and keys sorted?
- shahzaib1019 September 22, 2016Simple solution- Run BFS and keep track of all the paths we have encountered from this node
struct Node{
char Name;
unordered_map<Node*, int> neighbors // hash table with corrosponding weight
}
void printSum(vector<Node*>& graph){
unordered_map<Node*, unordered_set<Node*>> paths; // all the paths we have for this node
int global_sum = 0;
for (Node* n : graph)
paths.insert(n,unordered_set<Node*>()); // initialize all nodes
for (Node* n : graph){
runBFS(n,global_sum,paths);
cout << global_sum<<endl;
}
void runBFS(Node* root, int& global_sum,unordered_map<Node*, unordered_set<Node*>>& paths){
Queue<pair<Node*,int>> q; /// queue with the path to this node
unordered_set<Node*> seen; // keep track of which nodes we have seen
q.push(make_pair(root,0));
seen.insert(root);
unordered_set<Node*> my_paths = paths.find(root)->second; // my paths
// start bfs
while (!q.empty()){
auto top = q.front(); // get the top
q.pop();
Node * visiting_node = top.first; // get the visiting node
// loop through neihbors
for (Node* neighbor: visiting_node->neighbors){
if (seen.find(neighboor) == seen.end()){
seen.add(neighbor);
auto temp = make_pair(neighbor->first,top->second+neighbor->second); // make pair with my distance plus my parents total distance
if (my_paths.find(neighbor->first) == my_paths.end()){ // i havent visited it
auto& neighbor_path = paths.find(neighbor->first)->second;
neigbor_path.insert(root); // we have a path from root to this guy
global_sum += temp->second; // update sum
} // end of visiting if
q.push(temp);
} // end of if
} // end of for
} // end of while
} // end of runBFS method
}
- shahzaib1019 September 22, 2016