????玄关

P3366 【模板】最小生成树

jingliang_youxi @ 2024-10-14 11:08:29

#include <bits/stdc++.h>
using namespace std;

struct node {
    int v, w;
};
int n, m;
vector<node>e[5005];
int dis[5005], book[5005]

int p() {
    priority_queue<pair<int, int>>q;
    q.push({0, 1});
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        q.push({-dis[i], i});
    }
    int cnt = 0;
    while (!q.empty()) {
        int tmp = q.top().second;
        int D = -q.top().first;
        q.pop();
        if (book[tmp] || D == 0x3f3f3f3f)
            continue;
        book[tmp] = 1;
        res += dis[tmp];
        cnt++;
        for (int i = 0; i < e[tmp].size(); i++) {
            int v = e[tmp][i].v;
            int w = e[tmp][i].w;
            if (dis[v] > w) {
                dis[v] = w;
                q.push({-dis[v], v});
            }
        }
    }
    if (cnt == n)
        return res;
    else
        return -1;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].push_back({y, z});
    }
    int res = p();
    if (res == -1) {
        cout << "orz" << endl;
    } else {
        cout << res << endl;
    }
    return 0;
}

by kingcen @ 2024-10-22 21:57:30


cnt是不是该等于n-1

|