Prim算法模板

             1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4usingnamespace std;
 5constint N=1001;
 6constint inf=1<<29;
 7int w[N][N];
 8int dis[N],flag[N];
 9int n,m,u,v,c;
10int  prim()
11{
12int sum=0;//计算最小距离13     memset(flag,0,sizeof(flag));
14for(int i=1; i<=n; i++)
15    {
16         dis[i]=w[1][i];//把起点到每个点的距离付给dis17    }
18     flag[1]=1;
19for(int i=1; i<n; i++)//会更新n-1次顶点，每个点都会做一次顶点20    {
21int to=-1,min1=inf;
22for(int j=1; j<=n; j++)//从起点开始找，求出各点到以找过的顶点的距离最小值23        {
24if(!flag[j]&&dis[j]<min1)//保证不是被使用过的顶点，重新算出此次循环的最小值25            {
26                 to=j;//把最小值对应的点的下标记录下27                 min1=dis[j];
28            }
29        }
30if(to==-1) return -1;//有断点，不能到达31         sum+=min1;
32         flag[to]=1;
33for(int j=1; j<=n; j++)
34        {
35             dis[j]=min(dis[j],w[to][j]);//更新顶点，其中存储着最短的目前找过的顶点与各点之间的距离36         }//这样方便以后可以直接找到与各点的最短距离，遇到回路也不怕！37    }
38return sum;
3940}
41int main()
42{
43while(scanf("%d%d",&n,&m)!=EOF)//n个顶点，m条边44    {
45for(int i=1; i<=n; i++) //初始化i到j点的距离为无穷大，46        {
47for(int j=1; j<=n; j++)
48            {
49                 w[i][j]=inf;//i到j，j到i 都要人为的付成是一样的50            }
51        }
52for(int i=0; i<m; i++)
53        {
54             scanf("%d%d%d",&u,&v,&c);//起点u，终点v，权值c55             w[u][v]=w[v][u]=c;
56        }
57         printf("%d\n",prim());
58    }
59return0;
60 }