Я пытаюсь решить задачу
1160. Network. Как мне кажется, для её решения нужно найти остовное дерево, поэтому я решил использовать алгоритм Прима. К сожалению, ошибка на тесте 5. Что может быть не так? Все мои тесты проходят.
#include <iostream>;
#include <vector>;
void primAlgorithm(std::vector<std::vector<int>>& matrix, std::vector<int>& parent, std::vector<int>& minValue, std::vector<bool>& isPartOfOutputTree)
{
minValue[0] = 0;
parent[0] = -1;
for (int i = 0; i < matrix.size(); i++)
{
int minIndex = -1;
for (int j = 0; j < matrix.size(); j++)
if ((!isPartOfOutputTree[j]) && ((minIndex == -1) || (minValue[minIndex] > minValue[j])))
minIndex = j;
isPartOfOutputTree[minIndex] = true;
for (int j = 0; j < matrix.size(); j++)
if ((matrix[minIndex][j] < minValue[j]))
{
parent[j] = minIndex;
minValue[j] = matrix[minIndex][j];
}
}
}
int main()
{
int n = 0, m = 0;
std::cin >> n >> m;
std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 1000001));
std::vector<int> parent(n), minValue(n, 1000001);
std::vector<bool> isPartOfOutputTree(n);
for (int i = 0; i < m; i++)
{
int first = 0, second = 0, length = 0;
std::cin >> first >> second >> length;
matrix[first - 1][second - 1] = length;
matrix[second - 1][first - 1] = length;
}
primAlgorithm(matrix, parent, minValue, isPartOfOutputTree);
int maxLength = matrix[1][parent[1]];
for (int i = 1; i < n; i++)
if (matrix[i][parent[i]] > maxLength) maxLength = matrix[i][parent[i]];
std::cout << maxLength << '\n' << n - 1 << '\n';
for (int i = 1; i < n; i++)
std::cout << parent[i] + 1 << ' ' << i + 1 << '\n';
}
