内置类型pair介绍

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
const int maxn=5e3+5, maxm=4e5+5;
int n, m, head[maxn], nxt[maxm], v[maxm], w[maxm], cnt, dis[maxn];
bool tag[maxn];                                         //标记点是否被加入MST 
void add(int x, int y, int z) { cnt++, v[cnt]=y, w[cnt]=z, nxt[cnt]=head[x], head[x]=cnt; }
int prim(int s)
{
    memset(dis, 0x7f, sizeof(dis));                     //清空dis数组 
    priority_queue<pii, vector<pii>, greater<pii> > Q;  //小根堆 
    int num=1, ans=0;                                   //num统计加入MST的点的数量，ans为MST边权和 
    tag[s] = true;
    for(int i=head[s]; i; i=nxt[i])
        if(v[i]!=s) Q.push(make_pair(w[i], v[i])), dis[v[i]]=min(dis[v[i]], w[i]);
    while(!Q.empty() && num!=n)
    {
        while(!Q.empty() && tag[Q.top().second]) Q.pop();//忽略已加入MST的点 
        if(Q.empty())   break;
        int x=Q.top().second;                           //最小dis 
        tag[x]=true, ans+=Q.top().first, num++;         //加入mst 
        Q.pop();
        for(int i=head[x]; i; i = nxt[i])               //使用x松弛与当前MST相连点的dis值
            if(!tag[v[i]] && dis[v[i]]>w[i])        Q.push(make_pair(w[i], v[i])), dis[v[i]]=w[i];
    }
    if (num!=n) return -1;
    else        return ans;
}

int main(void)
{
    scanf("%d%d", &n, &m);
    for(int i=1, x, y, z; i<=m; i++)                    //x, y, z放在for内定义可以省一行空间 
        scanf("%d%d%d", &x, &y, &z), add(x, y, z), add(y, x, z);
    int ans=prim(1);
    if(ans!=-1) printf("%d\n", ans);
    else        printf("orz\n");
    return 0;
}