最小生成ツリー——Primアルゴリズム(C++)

   ：

#include
#include
int m,n,i[1001][1001],h[1001];
bool f[1001]={0};
long long ans(0);
int main()
{
    memset(h,0x3f,sizeof(h));  //      ，      ，           。
    h[1]=0;  //    1       。
    scanf("%d%d",&n,&m);
    for (int a=1;a<=m;a++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        i[x][y]=i[y][x]=z;  //       。
    }
    for (int a=1;a<=n;a++) //      。
    {
    　　int t(0);
    　　for (int b=1;b<=n;b++)
      　　if (!f[b]&&(h[b]<h[t]))
        　　t=b;
    　　f[t]=true;
    　　for (int b=1;b<=n;b++)
      　　if (!f[b]&&(h[b]>i[t][b]))
        　　h[b]=i[t][b];
    }  //   Dijkstra  。
    for (int a=1;a<=n;a++)
      ans+=h[a];  //                 ，      。
    printf("%d",ans);
    return 0;
}

転載先:https://www.cnblogs.com/koruko/p/5100226.html