无向图最小生成树（prim算法）

输入

第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000) 第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)

输出

输出最小生成树的所有边的权值之和。

输入示例

9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

输出示例

37

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 1005
#define INF 0x7fffffff

int N,M,S,E,W;
vector<vector<int> > val(MAX,vector<int>(MAX,INF));

long long prim(){
long long res=0;
vector<bool> vis(MAX,false);
vector<int> min(MAX,INF);
min[1]=0;
for(int i=1;i<=N;i++){
int j,k;
for(k=-1,j=1;j<=N;j++)
if(!vis[j]&&(k==-1||min[j]<min[k]))
k=j;
vis[k]=1;
res+=min[k];
for(int i=1;i<=N;i++)
if(!vis[i]&&val[k][i]<min[i])
min[i]=val[k][i];
}
return res;
}
int main(){

cin>>N>>M;
for(int i=0;i<M;i++){
cin>>S>>E>>W;
val[S][E]=val[E][S]=W;
}
cout<<prim()<<endl;
return 0;
}