PRIM (prototype)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int V, E; // Кол-во вершин и рёбер в графе соответственно
vector<vector<int>> graph; // Список смежности исходного графа
vector<vector<int>> mst; // Минимальное остовное дерево
vector<vector<int>> weight; // Веса рёбер. weigt[i][j] - вес ребра (i,j)
vector<int> d; // Расстояние от i-ой вершины до mst
vector<int> p; // Предок i-ой вершины. У (p[i], i) минимальный вес(для mst)
vector<int> q; // Приоритетная очередь, где ключ d[i]
int mst_weight = 0;

/*----------- Заполнение списка смежности + ----------------------------------*/
void read_graph() {
  cin >> V >> E;

  graph.resize(V);
  weight.assign(V, vector<int>(V, 100001));

  int begin, end, w; // Начальная вершина ребра, конечная, вес ребра
  for (int i = 0; i < E; i++) {
    cin >> begin >> end >> w;
    graph[begin - 1].push_back(end - 1);
    graph[end - 1].push_back(begin - 1); // Тк граф неориентированный
    weight[begin - 1][end - 1] = w;
    weight[end - 1][begin - 1] = w;
  }
}
/*----------- Проверить есть ли ещё вершины в q ------------------------------*/
bool q_empty() {
  for (int i = 0; i < V; i++) // Идём по всей очереди
    if (q[i] != -1) // если есть хоть одна вершина
      return false; // то очередь не пустая
  return true;
}
/*----------- Поиск вершины с минимальным расстоянием до остовного дерева ----*/
int extract_min() {
  int min = 0; // Индекс вершины с минимальным расстоянием до остовного дерева
  for (int i = 1; i < V; i++) // Идём по всем вершинам
    if (d[i] < d[min]) // и ищем минимальное расстояние до остовного дерева
      min = i;
  q[min] = -1; // Вершина с индексом min отработанна и её в очереди больше нет
  d[min] = 100001; // Чтобы не выбирались новые вершины
  return min;
}
/*----------- Проверить есть ли вершина в q ----------------------------------*/
bool in_q(int vertex) { // Передаём индекс вершины
  if (q[i] == -1) // Если вершина == -1 => её нет в очереди
    return false;
  return true;
}
/*----------- Алгоритм Прима -------------------------------------------------*/
void prim_find_mst() {
  mst.resize(V);       // В mst изначально ничего нет
  d.assign(V, 100001); // Всем вершинам задаём бесконечно большое расстояние
  p.assign(V, -1); // У всех вершин изначально нет родителя
  d[0] = 0; // Вершина 0 стартовая и уже входит в mst

  q.resize(V);                // В q сейчас ровно V нулей
  for (int j = 0; j < V; j++) // но надо чтобы было 0, 1, 2, ..., V-1
    q[j] = j;

  int vertex = extract_min(); // Извлечётся вершина с индексом 0

  while (!q_empty()) { // Пока не пербрали все вершины
    for (auto adjacent : graph[vertex]) // идём по всем вершинам смежным vertex
      if (weight[vertex][adjacent] < d[adjacent] && in_q(adjacent)) {
        d[adjacent] = weight[adjacent][vertex]; // Задаём расстояние и
        p[adjacent] = vertex; // предка для смежной вершины
      }

    vertex = extract_min();

    // mst[p[vertex]].push_back(vertex);
    // mst[vertex].push_back(p[vertex]);
    mst_weight += weight[p[vertex]][vertex];
  }
  cout << mst_weight << endl;
}
/*----------------------------------------------------------------------------*/
int main() {

  freopen("spantree3.in", "r", stdin);
  // freopen("spantree3.out", "w", stdout);

  read_graph();
  prim_find_mst();

  return 0;
}