Networking POJ - 1287

题目链接：https://vjudge.net/problem/POJ-1287

思路：最小生成树板子题

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <stack>

#include <string>

#include <map>

#include <cmath>

#include <iomanip>

using namespace std;

typedef long long LL;

#define inf 1e9

#define rep(i,j,k) for(int i = (j); i <= (k); i++)

#define rep__(i,j,k) for(int i = (j); i < (k); i++)

#define per(i,j,k) for(int i = (j); i >= (k); i--)

#define per__(i,j,k) for(int i = (j); i > (k); i--)

const int N = ;

int head[N];

int dis[N];

bool vis[N];

int cnt;

int n,m;

struct Edge{

    int to;

    int w;

    int nxt;

}e[N*N];

struct node{

    int u;

    int w;

    friend bool operator<(const node& a,const node& b){

        return a.w > b.w;

    }

};

priority_queue<node> que;

void add(int u,int v,int w){

    e[cnt].to = v;

    e[cnt].w = w;

    e[cnt].nxt = head[u];

    head[u] = cnt++;

}

int prime(){

    while(!que.empty()) que.pop();

    rep(i,,n){

        vis[i] = false;

        dis[i] = inf;

    }

    dis[] = ;

    que.push(node{,dis[]});

    int u,v,w;

    while(!que.empty()){

        u = que.top().u;

        que.pop();

        if(vis[u]) continue;

        vis[u] = true;

        for(int o = head[u]; ~o; o = e[o].nxt){

            v = e[o].to;

            w = e[o].w;

            if(!vis[v] && dis[v] > w){

                dis[v] = w;

                que.push(node{v,dis[v]});

            }

        }

    }

    int ans = ;

    rep(i,,n) ans += dis[i];

    return ans;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie();

    int u,v,w;

    while(cin >> n && n){

        cin >> m;

        rep(i,,n) head[i] = -;

        cnt = ;

        rep(i,,m){

            cin >> u >> v >> w;

            add(u,v,w);

            add(v,u,w);

        }

        cout << prime() << endl;

    }

    return ;

}