50   CostMap extended_dijkstra(const DistGraph &g, std::string start_node) {
 51   //3a
 52   CostMap info_map;
 53   CostMap answer_map;
 54   //3b
 55   CostPQ sorter;
 56
 57   for (auto nodes : g.all_nodes()){
 58     Info inf = Info(nodes.first);
 59     if (nodes.first == start_node)
 60         inf.cost = 0;
 61     info_map[nodes.first] = inf;
 62     sorter.enqueue(inf);
 63   }
 64   //3c
 65   while(!info_map.empty()){
 66     //3c1
 67     Info current = sorter.dequeue();
 68     //3c2
 69     std::string min_node = current.node;
 70     int min_cost = current.cost;
 71     if (min_cost == std::numeric_limits<int>::max())
 72         break;
 73     //std::cout << info_map << std::endl;
 74     if (!answer_map.has_key(min_node)){
 75         //3c3
 76         answer_map[min_node] = info_map[min_node];
 77         info_map.erase(min_node);
 78
 79         //3c4
 80         for (const auto d : g.out_nodes(min_node)){
 81             if (!answer_map.has_key(d)){
 82                 int real_cost  = min_cost + g.edge_value(min_node, d);
 83                 Info &inf = info_map[d];
 84                 if (real_cost < inf.cost){
 85                     //1
 86                     inf.cost = real_cost;
 87                     inf.from = min_node;
 88                     //2
 89                     sorter.enqueue(inf);
 90                 }
 91             }
 92         }
 93     }
 94   }
 95   //3d
 96   return answer_map;
 97   }