text: #include "init.hpp"
  
  inline void steiner_3(const vector<map<Vertex, Weight>> &adjList,
                        vector<Weight> &min_distance0, vector<Vertex> &origin0,
                        Vertex v0, Vertex v1, Vertex v2) {
    vector<Weight> min_distance1(adjList.size(), MAX_WEIGHT);
    vector<Vertex> origin1(adjList.size(), -1);
    vector<Weight> min_distance2(adjList.size(), MAX_WEIGHT);
    vector<Vertex> origin2(adjList.size(), -1);
  
    dijkstra(adjList, min_distance1, origin1, v1, v0, v2);
    if (min_distance0[v2] == min_distance1[v2]) {
      dijkstra(adjList, min_distance2, origin2, v2, v0, v1);
    } else {
      if (min_distance0[v2] < min_distance1[v2]) {
        dijkstra(adjList, min_distance2, origin2, v2, v0);
      } else {
        dijkstra(adjList, min_distance2, origin2, v2, v1);
      }
    }
    Vertex intersect = -1;
    Weight distIntersect = MAX_WEIGHT;
    for (unsigned int i = 0; i < adjList.size(); ++i) {
      if (min_distance2[i] != MAX_WEIGHT && min_distance1[i] != MAX_WEIGHT &&
          min_distance0[i] != MAX_WEIGHT &&
          min_distance0[i] + min_distance1[i] + min_distance2[i] <
              distIntersect) {
        intersect = i;
        distIntersect = min_distance0[i] + min_distance1[i] + min_distance2[i];
      }
    }
    // Fill seen
    vector<bool> seen(adjList.size(), false);
    Vertex current = intersect;
    while (origin0[current] != -1) {
      seen[current] = true;
      current = origin0[current];
    }
    seen[current] = true;
    // Merge origin1 into origin0
    current = intersect;
    while (origin1[current] != -1) {
      if (!seen[origin1[current]]) {
        origin0[origin1[current]] = current;
      }
      seen[current] = true;
      current = origin1[current];
    }
    seen[current] = true;
    // Merge origin2 into origin0
    current = intersect;
    while (origin2[current] != -1) {
      if (!seen[origin2[current]]) {
        origin0[origin2[current]] = current;
      }
      current = origin2[current];
    }
  }
  
  Tree incrementalDijks3(const Graph &G, Vertex root,
                         const vector<int> &terminalsMap,
                         const vector<Vertex> &terminals) {
    vector<std::map<Vertex, Weight>> adjList = G.adjList;
    vector<Weight> min_distance(G.adjList.size(), MAX_WEIGHT);
    vector<Vertex> origin(G.adjList.size(), -1);
    Vertex far = dijkstra(adjList, min_distance, origin, root, terminalsMap,
                          terminals.size());
    Weight far_dist = min_distance[far];
  
    Vertex last_far = far;
    bool dijk_simple = true;
    while (far_dist > 0 && !tle) {
      if (dijk_simple) {
        dijk_simple = false;
        vector<Weight> copy_distance = min_distance;
        vector<Vertex> copy_origin = origin;
  
        // Update graph, set edge to 0
        last_far = far;
        Vertex current = far;
        while (origin[current] != -1 && copy_distance[current] != 0) {
          copy_distance[current] = 0;
          current = origin[current];
        }
        current = far;
        set<pair<Weight, Vertex>> active_vertices;
        while (origin[current] != -1 && min_distance[current] != 0) {
          for (map<Vertex, Weight>::const_iterator it = adjList[current].begin();
               it != adjList[current].end(); ++it) {
            if (it->first != copy_origin[current] &&
                copy_distance[it->first] > it->second) {
              active_vertices.erase({copy_distance[it->first], it->first});
              active_vertices.insert({it->second, it->first});
              copy_distance[it->first] = it->second;
              copy_origin[it->first] = current;
            }
          }
          current = origin[current];
        }
        dijkstra(adjList, copy_distance, copy_origin, active_vertices);
        far_dist = 0;
        for (vector<Vertex>::const_iterator it = terminals.begin();
             it != terminals.end(); ++it) {
          if (far_dist < copy_distance[*it]) {
            far_dist = copy_distance[*it];
            far = *it;
          }
        }
      } else {
        dijk_simple = true;
        steiner_3(adjList, min_distance, origin, root, far, last_far);
  
        // Update graph
        Vertex current = far;
        while (origin[current] != -1) {
          adjList[current][origin[current]] = 0;
          adjList[origin[current]][current] = 0;
          min_distance[current] = MAX_WEIGHT;
          current = origin[current];
        }
        current = last_far;
        while (origin[current] != -1) {
          adjList[current][origin[current]] = 0;
          adjList[origin[current]][current] = 0;
          min_distance[current] = MAX_WEIGHT;
          current = origin[current];
        }
        dijkstra(adjList, min_distance, origin, root);
        far_dist = 0;
        for (vector<Vertex>::const_iterator it = terminals.begin();
             it != terminals.end(); ++it) {
          if (far_dist < min_distance[*it]) {
            far_dist = min_distance[*it];
            far = *it;
          }
        }
      }
    }
  
    // Build tree
    Tree T(G, root);
    for (unsigned int i = 0; i < G.adjList.size(); ++i) {
      if (origin[i] != -1) {
        T.tree[i].parent = origin[i];
        T.tree[i].weight = G.adjList[i].find(origin[i])->second;
        T.tree[origin[i]].children.insert(i);
      }
    }
    return T;
  }
  
  Tree incrementalOptDijks3(const Graph &G, Vertex root,
                            const vector<int> &terminalsMap,
                            const vector<Vertex> &terminals) {
    vector<std::map<Vertex, Weight>> adjList = G.adjList;
    vector<Weight> min_distance(G.adjList.size(), MAX_WEIGHT);
    vector<Vertex> origin(G.adjList.size(), -1);
    Vertex far = dijkstra(adjList, min_distance, origin, root, terminalsMap,
                          terminals.size());
    Weight far_dist = min_distance[far];
  
    vector<Weight> full_backup_distance = min_distance;
    vector<Vertex> full_backup_origin = origin;
  
    vector<Vertex> current_terminals;
    vector<int> current_terminalsMap(terminalsMap.size(), -1);
    current_terminals.reserve(terminals.size());
  
    Vertex last_far = far;
    while (far_dist > 0 && !tle) {
      bool dijk_simple = true;
      for (int i = 0; i < 4 && far_dist > 0 && !tle; ++i) {
        if (dijk_simple) {
          current_terminalsMap[far] = current_terminals.size();
          current_terminals.push_back(far);
          dijk_simple = false;
          vector<Weight> backup_distance = min_distance;
          vector<Vertex> backup_origin = origin;
  
          // Update graph, set edge to 0
          last_far = far;
          Vertex current = far;
          while (origin[current] != -1 && min_distance[current] != 0) {
            backup_distance[current] = 0;
            current = origin[current];
          }
          current = far;
          set<pair<Weight, Vertex>> active_vertices;
          while (origin[current] != -1 && min_distance[current] != 0) {
            for (map<Vertex, Weight>::iterator it = adjList[current].begin();
                 it != adjList[current].end(); ++it) {
              if (backup_distance[it->first] > it->second) {
                active_vertices.erase({backup_distance[it->first], it->first});
                active_vertices.insert({it->second, it->first});
                backup_distance[it->first] = it->second;
                backup_origin[it->first] = current;
              }
            }
            current = origin[current];
          }
          dijkstra(adjList, backup_distance, backup_origin, active_vertices);
          far_dist = 0;
          for (vector<Vertex>::const_iterator it = terminals.begin();
               it != terminals.end(); ++it) {
            if (far_dist < backup_distance[*it]) {
              far_dist = backup_distance[*it];
              far = *it;
            }
          }
        } else {
          dijk_simple = true;
          current_terminalsMap[far] = current_terminals.size();
          current_terminals.push_back(far);
          steiner_3(adjList, min_distance, origin, root, far, last_far);
  
          // Update graph
          Vertex current = far;
          while (origin[current] != -1) {
            adjList[current][origin[current]] = 0;
            adjList[origin[current]][current] = 0;
            min_distance[current] = MAX_WEIGHT;
            current = origin[current];
          }
          current = last_far;
          while (origin[current] != -1) {
            adjList[current][origin[current]] = 0;
            adjList[origin[current]][current] = 0;
            min_distance[current] = MAX_WEIGHT;
            current = origin[current];
          }
          dijkstra(adjList, min_distance, origin, root);
          far_dist = 0;
          for (vector<Vertex>::const_iterator it = terminals.begin();
               it != terminals.end(); ++it) {
            if (far_dist < min_distance[*it]) {
              far_dist = min_distance[*it];
              far = *it;
            }
          }
        }
      }
  
      Tree T(G, root);
      for (unsigned int i = 0; i < G.adjList.size(); ++i) {
        if (origin[i] != -1) {
          T.tree[i].parent = origin[i];
          T.tree[i].weight = G.adjList[i].find(origin[i])->second;
          T.tree[origin[i]].children.insert(i);
        }
      }
      Weight oldw, w = T.pruneLeaves(G.terminalsMap);
      do {
        if (tle)
          break;
        oldw = w;
        apply_opt(T, G);
        w = T.pruneLeaves(G.terminalsMap);
      } while (oldw != w);
  
      if (tle)
        break;
      adjList = G.adjList;
      origin = full_backup_origin;
      min_distance = full_backup_distance;
      stack<Vertex> next;
      next.push(T.root);
      while (!next.empty()) {
        Vertex current = next.top();
        next.pop();
        for (set<Vertex>::iterator it = T.tree[current].children.begin();
             it != T.tree[current].children.end(); ++it) {
          next.push(*it);
          min_distance[*it] = MAX_WEIGHT;
          origin[*it] = -1;
          adjList[current][*it] = 0;
          adjList[*it][current] = 0;
        }
      }
      if (tle)
        break;
      dijkstra(adjList, min_distance, origin, root);
      far_dist = 0;
      for (vector<Vertex>::const_iterator it = terminals.begin();
           it != terminals.end(); ++it) {
        if (far_dist < min_distance[*it]) {
          far_dist = min_distance[*it];
          far = *it;
        }
      }
    }
  
    // Build tree
    Tree T(G, root);
    for (unsigned int i = 0; i < G.adjList.size(); ++i) {
      if (origin[i] != -1) {
        T.tree[i].parent = origin[i];
        T.tree[i].weight = G.adjList[i].find(origin[i])->second;
        T.tree[origin[i]].children.insert(i);
      }
    }
    return T;
  }
  bool cmp(const tuple<Weight, Vertex, Vertex> &x,
           const tuple<Weight, Vertex, Vertex> &y) {
    return get<0>(x) > get<0>(y);
  }
  
  Tree mst(const Graph &G, Vertex root) {
    Tree T(G, root);
    vector<tuple<Weight, Vertex, Vertex>> active_vertices;
    for (pair<Vertex, Weight> neighbour : G.adjList[root]) {
      active_vertices.push_back(
          tuple<Weight, Vertex, Vertex>(neighbour.second, root, neighbour.first));
    }
    make_heap(active_vertices.begin(), active_vertices.end(), cmp);
    while (!active_vertices.empty()) {
      std::pop_heap(active_vertices.begin(), active_vertices.end(), cmp);
      tuple<Weight, Vertex, Vertex> edge = active_vertices.back();
      active_vertices.pop_back();
      if (T.tree[get<2>(edge)].parent == -2) {
        T.tree[get<2>(edge)].parent = get<1>(edge);
        T.tree[get<2>(edge)].weight = get<0>(edge);
        T.tree[get<1>(edge)].children.insert(get<2>(edge));
        for (pair<Vertex, Weight> neighbour : G.adjList[get<2>(edge)]) {
          if (T.tree[neighbour.first].parent == -2) {
            active_vertices.push_back(tuple<Weight, Vertex, Vertex>(
                neighbour.second, get<2>(edge), neighbour.first));
            push_heap(active_vertices.begin(), active_vertices.end(), cmp);
          }
        }
      }
    }
    return T;
  }
  
  Tree strong_bias_random(const Graph &G, Vertex root) {
    Tree T(G, root);
    default_random_engine generator;
    vector<tuple<Weight, Vertex, Vertex>> active_vertices;
    for (pair<Vertex, Weight> neighbour : G.adjList[root]) {
      active_vertices.push_back(
          tuple<Weight, Vertex, Vertex>(neighbour.second, root, neighbour.first));
    }
    while (!active_vertices.empty()) {
      int position =
          uniform_int_distribution<int>(0, active_vertices.size() - 1)(generator);
      tuple<Weight, Vertex, Vertex> edge = active_vertices[position];
      active_vertices[position] = active_vertices.back();
      active_vertices.pop_back();
      if (T.tree[get<2>(edge)].parent == -2) {
        T.tree[get<2>(edge)].parent = get<1>(edge);
        T.tree[get<2>(edge)].weight = get<0>(edge);
        T.tree[get<1>(edge)].children.insert(get<2>(edge));
        for (pair<Vertex, Weight> neighbour : G.adjList[get<2>(edge)]) {
          if (T.tree[neighbour.first].parent == -2) {
            active_vertices.push_back(tuple<Weight, Vertex, Vertex>(
                neighbour.second, get<2>(edge), neighbour.first));
            push_heap(active_vertices.begin(), active_vertices.end(), cmp);
          }
        }
      }
    }
    return T;
  }
  
  Tree random(const Graph &G, Vertex root) {
    vector<Vertex> origin(G.adjList.size(), -2);
    origin[root] = -1;
    default_random_engine generator;
    for (Vertex t : G.terminals) {
      vector<bool> seen(G.adjList.size(), false);
      Vertex current = t;
      while (origin[current] == -2 || seen[current]) {
        seen[current] = true;
        int position = uniform_int_distribution<int>(
            0, G.adjList[current].size() - 1)(generator);
        map<Vertex, Weight>::const_iterator it = G.adjList[current].begin();
        advance(it, position);
        Vertex next = it->first;
        origin[current] = next;
        current = next;
      }
    }
    Tree T(G, root);
    for (unsigned int i = 0; i < G.adjList.size(); ++i) {
      if (origin[i] > -1) {
        T.tree[i].parent = origin[i];
        T.tree[i].weight = G.adjList[i].find(origin[i])->second;
        T.tree[origin[i]].children.insert(i);
      }
    }
    return T;
  }
  