重铸华农荣光 我辈义不容辞

The eighteenth day - Prim

Prim 算法的模板与Dijkstra算法高度相似，但是dist[t]含义不同，Dijkstra中的dist[t]含义很简单，就是点1到点t的距离，而Prim中dist[t]为点t到目标集合的距离

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=510;
int g[N][N],dist[N],st[N],pre[N];
int n,m;

void prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    dist[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++) 
            if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;\
        if(dist[t]==0x3f3f3f3f)
        {
            cout<<"impossible";
            return;
        }
        st[t]=1;
        res+=dist[t];
        for(int i=1;i<=n;i++)
        {
            if(dist[i]>g[t][i]&&!st[i])
            {
                dist[i]=g[t][i];
                pre[i]=t;
            }
        }
    }

    cout<<res;
}

void getPath()
{
    for(int i=n;i>1;i--)
    {
        cout<<i<<" "<<pre[i]<<" "<<endl;
    }
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b]=g[b][a]=min(g[a][b],w);
    }

    prim();
//  getPath();
    return 0;
}