Поиск кратчайшего пути в графе

Дан неориентированный граф, длины ребер в котором равны 0 или 1. Необходимо найти длину кратчайшего пути из вершины A в вершину B.
В первой строке входа задано 4 целых числа n, m, a, b количество вершин и ребер графа, номер вершины A и номер вершины B соответственно. Вершины пронумерованы от 1 до n. 1 ≤ m, n ≤ 100 000, 1 ≤ a, b ≤ n. В каждой из следующих m строк по три целых числа, первое из которых означает номер начальной вершины ребра, второе номер конечной вершины ребра, третье длину ребра (0 или 1).
Выведите длину кратчайшего пути из вершины A в вершину B . Если пути из A в B не существует, выведите -1.

#include <stdio.h>
#include <vector>
#include <algorithm>

using std::vector;
using std::swap;

const int kMaxDistance = 1000000;

struct NodeLengthPair {
  int node_;
  int length_;

  NodeLengthPair(int node, int length):
    node_(node), length_(length) {}
};

struct DistancePositionPair {
  int distance_;
  int heap_position_;
  DistancePositionPair(int distance, int heap_position):
    distance_(distance), heap_position_(heap_position) {}
};

void ReadInput(vector< vector<NodeLengthPair> >& graph_edges,
               int& source_node,
               int& destination_node) {
  int nodes_num, edges_num, source, destination;
  scanf("%d %d %d %d", &nodes_num, &edges_num, &source, &destination);
  graph_edges.resize(nodes_num);
  source_node = source - 1;
  destination_node = destination - 1;
  int node_from, node_to, length;
  for (int counter = 0; counter < edges_num; ++counter) {
    scanf("%d %d %d", &node_from, &node_to, &length);
    graph_edges[node_from - 1].push_back(NodeLengthPair(node_to - 1, length));
    graph_edges[node_to - 1].push_back(NodeLengthPair(node_from - 1, length));
  }
}

void Heapify(int root_index,
             vector<int>& nodes_heap,
             vector<DistancePositionPair>& distance) {
  int left_son_index, right_son_index, smallest_index;
  left_son_index = 2 * root_index + 1;
  right_son_index = 2 * root_index + 2;
  smallest_index = root_index;
  if (left_son_index < nodes_heap.size() &&
      distance[nodes_heap[left_son_index]].distance_ <
          distance[nodes_heap[smallest_index]].distance_) {
    smallest_index = left_son_index;
  }
  if (right_son_index < nodes_heap.size() &&
      distance[nodes_heap[right_son_index]].distance_ <
          distance[nodes_heap[smallest_index]].distance_) {
    smallest_index = right_son_index;
  }
  if (smallest_index != root_index) {
    swap(distance[nodes_heap[root_index]].heap_position_,
         distance[nodes_heap[smallest_index]].heap_position_);
    swap(nodes_heap[root_index], nodes_heap[smallest_index]);
    Heapify(smallest_index, nodes_heap, distance);
  }
}

void MakeHeap(vector<int>& nodes_heap,
              vector<DistancePositionPair>& distance) {
  for (int counter = nodes_heap.size() / 2; counter >= 0; --counter) {
    Heapify(counter, nodes_heap, distance);
  }
}

int ExtractMin(vector<int>& nodes_heap,
               vector<DistancePositionPair>& distance) {
  int min = nodes_heap.front();
  nodes_heap.front() = nodes_heap.back();
  nodes_heap.pop_back();
  distance[nodes_heap.front()].heap_position_ = 0;
  Heapify(0, nodes_heap, distance);
  return min;
}

void ShiftUp(int index,
            vector<int>& nodes_heap,
            vector<DistancePositionPair>& distance) {
  if (index == 0) {
    return;
  }
  int parent_index = index % 2 == 0 ? (index - 2) / 2 : index / 2;
  if (distance[nodes_heap[parent_index]].distance_ >
          distance[nodes_heap[index]].distance_) {
    swap(distance[nodes_heap[parent_index]].heap_position_,
         distance[nodes_heap[index]].heap_position_);
    swap(nodes_heap[parent_index], nodes_heap[index]);
    ShiftUp(parent_index, nodes_heap, distance);
  }
}

int FindMinPath(const vector< vector<NodeLengthPair> >& graph_edges,
              int source_node,
              int destination_node) {
  vector<DistancePositionPair> distance(graph_edges.size(),
      DistancePositionPair(kMaxDistance, 0));
  distance[source_node].distance_ = 0;
  vector<int> nodes_heap(graph_edges.size());
  for (int counter = 0; counter < nodes_heap.size(); ++counter) {
    nodes_heap[counter] = counter;
    distance[counter].heap_position_ =  counter;
  }
  MakeHeap(nodes_heap, distance);
  int current_node;
  while (!nodes_heap.empty()) {
    current_node = ExtractMin(nodes_heap, distance);
    if (current_node == destination_node) {
      break;
    }
    for (vector<NodeLengthPair>::const_iterator adjanced_it =
             graph_edges[current_node].begin();
         adjanced_it != graph_edges[current_node].end();
         ++adjanced_it) {
      if (distance[adjanced_it->node_].distance_ >
              distance[current_node].distance_ + adjanced_it->length_) {
        distance[adjanced_it->node_].distance_ =
            distance[current_node].distance_ + adjanced_it->length_;
        ShiftUp(distance[adjanced_it->node_].heap_position_,
                nodes_heap,
                distance);
      }
    }
  }
  return distance[destination_node].distance_ == kMaxDistance ?
        -1 : distance[destination_node].distance_;
}

int main() {
  vector< vector<NodeLengthPair> > graph_edges;
  int source_node, destination_node;
  ReadInput(graph_edges, source_node, destination_node);
  printf("%d\n", FindMinPath(graph_edges, source_node, destination_node));
  return 0;
}

Поиск моста в неориентированном графе

Хонти хочет начать войну против Пандеи. План Хонти состоит в том, чтобы используя эффект неожиданности навести ужас на пандейцев, создать хаос, и в этих условиях быстро завоевать страну. Чтобы успешно воплотить этот план в жизнь, хонтийцам необходимо провести первую, самую важную операцию.
Цель операции разделить Пандею на две несвязанные части, разрушив всего лишь
одну дорогу (изначально карта Пандеи представляет собой связный граф). Хонтийская разведка уже добыла карты Пандеи, передала их экспертам, которые провели исследование и выяснили стоимость разрушения каждой из дорог страны-противника. Вам передали карту всех дорог вместе со стоимостями их разрушения. Вам нужно выбрать самую дешевую дорогу, удовлетворяющую запросам хонтийцев: предстоящая война еще потребует значительных ресурсов.
В первой строке входа заданы два целых числа n и m количество городов и количество дорог Пандеи соответственно. Дороги в Пандее двусторонние. В каждой из следующих m строк по три числа a, b и c номера начального и конечного горо дов дороги (города нумеруются с единицы) и стоимость разрушения данной дороги. 1 ≤ m, n ≤ 50 000. 1 ≤ a, b ≤ n. a = b. 1 ≤ c ≤ 1 000 000 000.
Выведите единственное число наименьшую стоимость дороги, которую можно разрушить, чтобы нарушить связность Пандеи. Если таких дорог не существует, выведите -1.

Проводится поиск в ширину, чтобы найти так называемые "мосты" - ребра, удаление которых, делает граф несвязным. Затем выбирается тот мост, разрушение которого самое дешевое.

#include<stdio.h>
#include<stack>
#include<vector>
#include<algorithm>

struct NodeCostPair {
  int node_;
  int cost_;

  NodeCostPair(int node, int cost):
    node_(node), cost_(cost) {}
};

struct ReturnInfo {
  int current_node_;
  int prev_node_;
  std::vector<NodeCostPair>::const_iterator node_it_;

  ReturnInfo(int current_node,
             int prev_node,
             std::vector<NodeCostPair>::const_iterator node_it):
    current_node_(current_node), prev_node_(prev_node), node_it_(node_it) {}
};

struct Edge {
  int node_from_;
  int node_to_;
  int cost_;

  Edge(int node_from, int node_to, int cost):
    node_from_(node_from), node_to_(node_to), cost_(cost) {}
};

enum Colors {
  WHITE = 0,
  GRAY = 1,
  BLACK = 2
};

template <typename T>
const T& min3(const T& a, const T& b, const T& c) {
  return std::min(a, std::min(b, c));
}

const int kMaxNodesNumber = 100000;

void DFS(const std::vector< std::vector<NodeCostPair> >& graph_edges,
         std::vector<int>& times_in,
         std::vector<int>& min_enter_time,
         std::vector<Edge>& dfs_edges) {
  std::stack<ReturnInfo> stack_nodes;
  std::vector<char> colors(graph_edges.size(), 0);
  int current_node = 0;  // Begin from the node 0.
  int prev_node = -1;
  int timer = 0;
  times_in.resize(graph_edges.size(), kMaxNodesNumber);
  times_in[0] = timer;
  min_enter_time.resize(graph_edges.size(), kMaxNodesNumber);
  bool go_deeper;
  bool exist_not_visited_nodes = true;
  std::vector<NodeCostPair>::const_iterator node_next_to_visit =
      graph_edges[current_node].begin();
  while (exist_not_visited_nodes) {
    colors[current_node] = GRAY;
    go_deeper = false;
    for (/* Loop initialization not needed. */;
         node_next_to_visit != graph_edges[current_node].end();
         ++node_next_to_visit) {
      if (node_next_to_visit->node_ != prev_node &&
          colors[node_next_to_visit->node_] == GRAY) {
        // Back edge.
        min_enter_time[current_node]
            = min3(times_in[node_next_to_visit->node_],
                   times_in[current_node],
                   min_enter_time[current_node]);
      }
      if (colors[node_next_to_visit->node_] == BLACK) {
        // Tree edge.
        min_enter_time[current_node]
            = min3(min_enter_time[node_next_to_visit->node_],
                   min_enter_time[current_node],
                   times_in[current_node]);
      }
      if (colors[node_next_to_visit->node_] == WHITE) {
        dfs_edges.push_back(Edge(current_node,
                                 node_next_to_visit->node_,
                                 node_next_to_visit->cost_));
        stack_nodes.push(ReturnInfo(current_node,
                                    prev_node,
                                    node_next_to_visit));
        prev_node = current_node;
        current_node = node_next_to_visit->node_;
        node_next_to_visit = graph_edges[current_node].begin();
        ++timer;
        times_in[current_node] = min_enter_time[current_node] = timer;
        go_deeper = true;
        break;
      }
    }
    if (!go_deeper) {
      colors[current_node] = BLACK;
      if (stack_nodes.empty()) {
        exist_not_visited_nodes = false;
      } else {
        // Return to the previous node
        current_node = stack_nodes.top().current_node_;
        prev_node = stack_nodes.top().prev_node_;
        node_next_to_visit = stack_nodes.top().node_it_;
        stack_nodes.pop();
      }
    }
  }
}

void ReadGraphEdges(std::vector< std::vector<NodeCostPair> >& graph_edges) {
  int nodes_num, edges_num;
  scanf("%d %d", &nodes_num, &edges_num);
  graph_edges.resize(nodes_num);
  int node_from, node_to, cost;
  for (int counter = 0; counter < edges_num; ++counter) {
    scanf("%d %d %d", &node_from, &node_to, &cost);
    graph_edges[node_from - 1].push_back(NodeCostPair(node_to - 1, cost));
    graph_edges[node_to - 1].push_back(NodeCostPair(node_from - 1, cost));
  }
}

const int kMinCost = -1;

int FindMinBridgeCost(const
                      std::vector< std::vector<NodeCostPair> >& graph_edges) {
  int min_cost = kMinCost;
  std::vector<int> times_in;
  std::vector<int> min_enter_time;
  std::vector<Edge> dfs_edges;
  DFS(graph_edges, times_in, min_enter_time, dfs_edges);
  for (std::vector<Edge>::const_iterator edge_it = dfs_edges.begin();
       edge_it != dfs_edges.end(); ++edge_it) {
    if (min_enter_time[edge_it->node_to_] > times_in[edge_it->node_from_]) {
      if (min_cost == -1) {
        min_cost = edge_it->cost_;
      } else {
        min_cost = std::min(min_cost, edge_it->cost_);
      }
    }
  }
  return min_cost;
}

int main() { 
  std::vector< std::vector<NodeCostPair> > graph_edges;
  ReadGraphEdges(graph_edges);
  printf("%d\n", FindMinBridgeCost(graph_edges));
  return 0;
}