Prime邻接表+优先队列

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xfffffff
#define maxn 103

struct Edge
{
    int e, w;
    Edge(int e=0,int w=0): e(e), w(w) {}
    friend bool operator < (Edge A, Edge B)
    {
        return A.w < B.w;
    }
};

vector<Edge> G[maxn];
int dist[maxn];
bool vis[maxn];
int m, n;
int Prime()
{
    Edge P, Pn;
    int Nnode = 0;
    dist[1] = 0;
    priority_queue < Edge > Q;
    Q.push( Edge(1,0) );

    while( !Q.empty() && Nnode < n )
    {
        while( !Q.empty() )
        {
            P = Q.top();
            Q.pop();
            if( !vis[P.e] )
                break;
        }
        if( vis[P.e] )
            continue;
        Nnode ++;
        vis[P.e] = true;
        int len = G[P.e].size();

        for(int i=0; i<len; i++)
        {
            Pn = G[P.e][i];

            if(!vis[Pn.e] && dist[Pn.e] > Pn.w)
            {
                dist[Pn.e] = Pn.w;
                Q.push(Pn);
            }
        }
    }
    if(Nnode < n)
        return -1;

    int sum = 0;
    for(int i=1; i<=n; i++)
    {
        sum += dist[i];
    }

    return sum;
}

void Init()
{
    for(int i=0; i<=n; i++)
    {
        G[i].clear();
        dist[i] = INF;
        vis[i] = false;
    }
}


int main()
{
    while(cin >> m >> n, m)
    {
        Init();
        for(int i=0; i<m; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;

            G[a].push_back( Edge(b,c) );
            G[b].push_back( Edge(a,c) );

        }

        int ans = Prime();

        if(ans == -1)
            cout << "?" << endl;
        else
            cout << ans << endl;

    }
    return 0;
}