Prim算法14分求调
查看原帖
Prim算法14分求调
952033
lutaoquan2012楼主2023/11/29 18:37
//
// Created by 55062 on 2023/11/29.
//
#include<bits/stdc++.h>
using namespace std;
int n,vis[5010],cost[5010],v[5010][5010],ans,m;//cost:每次到第i个点的最短距离
int main(){
    cin>>n>>m;
    memset(cost,0x3f,sizeof(cost));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) v[i][j]=-1;
    for(int i=1;i<=m;i++){
        int u,vv,w;
        cin>>u>>vv>>w;
        v[u][vv]=w;
        v[vv][u]=w;
    }
    cost[1]=0;
    for(int i=1;i<=n;i++) v[i][i]=0;
    for(int i=1;i<=n;i++){
        int u=0;
        for(int j=1;j<=n;j++)
            if(v[i][j]!=-1&&vis[j]==0&&cost[j]<cost[u]) u=j;
        ans+=cost[u];
        vis[u]=1;
        for(int j=1;j<=n;j++)
            if(v[i][j]!=-1&&vis[j]==0&&cost[j]>v[u][j]) cost[j]=v[u][j];
    }for(int i=1;i<=n;i++)
        if(cost[i]>=0x3f3f3f3f){
            cout<<"orz";
            exit(0);
        }
    cout<<ans;
    return 0;
}
2023/11/29 18:37
加载中...