30 堆邻接表prim求调

#include<bits/stdc++.h>
#define MAX_N 5000
#define MAX_E 200010
#define INF 0x3f3f3f3f

int res = 0;
int n, e;
using namespace std;

struct edge
{
    int to, cost;
};

vector<edge> G[MAX_E];
bool used[MAX_N];

void add(int a, int b, int c)
{
    edge e;
    e.to = b;
    e.cost = c;
    G[a].push_back(e);
}

typedef pair<int, int> p;
int dis[MAX_N];
int prim(int s)
{
    int cnt = 0;
    priority_queue<p, vector<p>, greater<p>> que;
    for (int i = 2; i <= n; i++)
        dis[i] = INF;
    que.push(p(s, 0));
    while (!que.empty()) {
        p P = que.top();
        que.pop();
        if (used[P.first])
            continue;
        used[P.first] = true;
        cnt++;
        int v = P.first, d = P.second;
        res += d;
        for (int i = 0; i < G[v].size(); i++) {
            if (!used[G[v][i].to] && G[v][i].cost < dis[G[v][i].to])
            {
                dis[G[v][i].to] = G[v][i].cost;
                que.push(p(G[v][i].to, G[v][i].cost));
            }
        }
    }
    if (cnt != n)
        return INF;
    return res;
}

int main()
{
    cin >> n >> e;
    int a, b, c;
    memset(dis, INF, sizeof(dis));
    for (int i = 1; i <= n; i++)
        used[i] = false;
    for (int i = 1; i <= e; i++) {
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    int ans = prim(1);
    if (ans == INF)
        cout << "orz";
    else
        cout << ans;
    return 0;
}