Description

给你一个具有n个点，m条边的无向连通图，求其最小生成树的权值和。

Input

第一行两个整数n(1<=n<=300)和m，分别表示图的顶点数和边数。

接下来m行是每行三个整数u, v, c，表示结点u和v之间有边相连，权值为c(1≤c≤10000)。

Output

输出文件仅一个整数为最小生成树的权值和。

Sample Input

3 3

1 2 5

2 3 3

1 3 1

Sample Output

4

#include<bits/stdc++.h>
#define inf 0x7fffffff
using namespace std;
int n,m;
struct eg
{
    int next,to,value;
}a[100000];
void fin(int &x)
{
    scanf("%d",&x);
}
int h[100000];
int cnt;
int d[100000];
int vis[100000];
int ans;
void Union(int x,int y,int z)
{
    cnt++;
    a[cnt].next=h[x];
    a[cnt].to=y;
    a[cnt].value=z;
    h[x]=cnt;
}
int main()
{
    fin(n);
    fin(m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fin(x);
        fin(y);
        fin(z);
        Union(x,y,z);
        Union(y,x,z);
    }
    fill(d+1,d+n+1,inf);
    d[1]=0;
    for(int i=1;i<=n;i++)
    {
        int minn=0x7fffffff;
        int k;
        for(int o=1;o<=n;o++)if(d[o]<minn&&vis[o]==0)minn=d[o],k=o;
        vis[k]=1;
        ans+=d[k];
        for(int o=h[k];o;o=a[o].next)
        {
            int to=a[o].to;
            if(vis[to]==0)
            {
                d[to]=min(d[to],a[o].value);
            }
        }
    }
    cout<<ans;
}

注意prim的状态转移方程

Prim：d[to]=min(d[to], a[o].value );

Dijkstra：d[to]=min(d[to], a[o].value+d[k] );

区别：

Prim: d[i]表示i节点到最小生成树的集合的最短距离

Dijkstra: d[i]表示i节点到单源点的最短距离

注意 一共prim了n次点，所以外层循环是1~n

但注意请勿犯

 for(int i=1;i<=n;i++)
 {
    for(int i=1;i<=n;i++)
    {
        ...
    }
 }

这样的错