原题链接：POJ1287
解析：这题我用来练习Prim算法的，算是当作一个模板来看。以下代码有几点要说明的：
- 我使用了优先队列，并没有使用dist[u]数组来保存当前子树到 u 的最短距离，这样省去了找最短路的时间
- 由于队列中存放的最短距离，可能该点已经存在子树中了，所以需要判断删除
代码实例：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int vis[105];//是否已经在子树中
int graph[105][105];
int p,r;
const int inf = 10e7;
struct Node{//用来在优先队列中存放数据
int val;
int id;
Node(int val,int id):val(val),id(id){}
};
bool operator < (const Node & a,const Node& b){//使用优先队列要重载小于运算符
return a.val > b.val;
}
int Prim(int cur){//从cur开始进行连接结点
int ans = 0;
priority_queue<Node> q;
memset(vis,0,sizeof vis);
for(int u = 1;u < p;u++){
vis[cur] = 1;
for(int i = 1;i <= p;i++)
if(!vis[i] && graph[cur][i] != inf)
q.push(Node(graph[cur][i],i));
Node h = q.top();
q.pop();
while(vis[h.id]){//如果当前最小距离的点已经全连接在子树里了，故删除
h = q.top();
q.pop();
}
cur = h.id;
ans += h.val;
}
return ans;
}
int main()
{
scanf("%d",&p);
while(p){
scanf("%d",&r);
int a,b,val;
for(int i = 1;i <= p;i++)
for(int j = 1;j <= p;j++) graph[i][j] = inf;
for(int i = 0;i < r;i++){
scanf("%d%d%d",&a,&b,&val);
graph[b][a] = graph[a][b] = min(val,graph[a][b]);
//俩个点直接最短距离
}
printf("%d
",Prim(1));
scanf("%d",&p);
}
return 0;
}