#8 #9 #10 RE求调

代码如下

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN = 5e3+100, MAXM = 2e5+10;

int n, m, cntEdge = -1, cnt = 0, res = 0;
int head[MAXN], nxt[MAXM], to[MAXM], w[MAXM];
int dis[MAXN], vis[MAXN];

void addEdge(int u, int v, int ew) {
    nxt[++cntEdge] = head[u];
    head[u] = cntEdge;
    to[cntEdge] = v;
    w[cntEdge] = ew;
}

struct node {
    int id, dis;
    node(int ndis, int u) {dis = ndis; id = u;}

    bool operator<(const node& n) const { return dis > n.dis; }
};

priority_queue<node > Q;

void prim() {
    dis[1] = 0;
    Q.push(node(0, 1));
    while (!Q.empty()) {
        if (cnt >= n) break;
        int u = Q.top().id, d = Q.top().dis;
        Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        ++cnt; res += d;
        for (int i=head[u];~i;i=nxt[i]) {
            int v = to[i], vw = w[i];
            if (dis[v] > vw) dis[v] = vw, Q.push(node(vw, v));
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(vis, 0, sizeof(vis));
    memset(dis, 0x7f3f3f3f, sizeof(dis));
    memset(head, -1, sizeof(head));
    memset(nxt, -1, sizeof(nxt)); 

    cin>>n>>m;
    for (int i=0, a, b, c;i<m;++i) cin>>a>>b>>c, addEdge(a, b ,c), addEdge(b, a ,c);

    prim();

    if (cnt == n) cout<<res;
    else cout<<"orz";

    return 0;
}