c++ - Prim算法应用

Question

大家，我有一个加权连通无向图，我需要找到它的最小生成树权重。在输入时，我有数字 n（顶点数量），m（边数量）。然后是 m 格式的边：A（out vert），B（in vert），C（weight）。这是输入示例：

3 3
1 2 1
2 3 2
3 1 3

我认为它是一个典型的 Prim 算法，所以我使用了它，但是一些测试告诉我我的代码给出了错误的答案。这里是：

#include <numeric>
#include <iostream>

using namespace std;

long long primAlgo(const int vertices, const vector<vector<long long>> &edges) {
    vector<bool> visited(vertices, false);
    vector<long long> minimal(vertices, 30001);

    minimal[0] = 0;
    for (size_t i = 0; i != vertices; ++i) {
        int vert = -1;
        for (size_t option = 0; option != vertices; ++option) {
            if (!visited[option] && (vert == -1 || minimal[option] < minimal[vert]))
                vert = option;
        }
        visited[vert] = true;

        for (size_t to = 0; to != vertices; ++to) {
            if (edges[vert][to] < minimal[to]) {
               minimal[to] = edges[vert][to];
            }
        }
    }

    long long sum = 0;

    for (size_t i = 0; i != vertices; ++i) {
        sum += minimal[i];
    }
    return sum;
}

int main() {
    int n, m;
    cin >> n >> m;
    int A, B;
    long long C;
    vector<vector<long long>> l(n, vector<long long> (n, 30001));
    for (size_t i = 0; i != m; ++i) {
        cin >> A >> B >> C;
        l[A - 1][B - 1] = C;
        l[B - 1][A - 1] = C;
    }

    long long ans = primAlgo(n, l);
    cout << ans;
}

所以我想知道，如果你知道，问题可能是什么。

标签： c++graphgraph-algorithmminimum-spanning-tree