Comment

wangjun-252392: 2026-01-06 18:05:13

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

const int MAXN = 505;
const int INF = INT_MAX;

vector<pair<int, int>> graph[MAXN]; 
vector<bool> visited(MAXN, false);
vector<int> dist(MAXN, INF); 

int prim(int n) {
    dist[1] = 0;
    int totalWeight = 0;

    for (int i = 1; i <= n; ++i) {
        int u = -1;
        for (int j = 1; j <= n; ++j) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        if (dist[u] == INF) {
            return -1; 
        }

        visited[u] = true;
        totalWeight += dist[u];
        for (const auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight;
            }
        }
    }

    return totalWeight;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n, E;
        cin >> n >> E;
        for (int i = 1; i <= n; ++i) {
            graph[i].clear();
            visited[i] = false;
            dist[i] = INF;
        }

        for (int i = 0; i < E; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].push_back(make_pair(v, w));
            graph[v].push_back(make_pair(u, w));
        }

        int result = prim(n);
        cout << result << endl;
    }

    return 0;
}

Huhu_Miao: 2024-12-02 21:21:10

写一个n^2的暴力dijkstra即可

dingchenkai: 2024-09-25 19:44:34

注意：①本题是无向图 ②原点为s，虽然样例输出中给出的原点均为1

Westbrook: 2024-05-31 16:53:45

切记考虑无向图，矩阵是对称矩阵

220222183陈友康: 2022-09-10 18:30:13

开了M个优先队列+二维迪杰斯特拉勉强过，正确做法应该是啥

214808: 2021-12-29 12:33:35

1