hihocoder1109最小生成树三·堆优化的Prim算法

题目链接：最小生成树三·堆优化的Prim算法

题目大意：给你一张无向带权图，求最小生成树

题目思路：采用堆优化的prim算法，具体算法讲解见：算法讲堂

时间复杂度&&空间复杂度：O（m*logm）&&O（max(n,m)）（n为点的个数，m为边的条数）

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
typedef pair<int,int>p;

vector
vec[maxn];
int vis[maxn];

int main(){
    int n,m,u,v,val;
    scanf("%d%d",&n,&m);
    memset(vis,0,sizeof(vis));
    for(int i = 1;i <= m;i++){
        scanf("%d%d%d",&u,&v,&val);
        vec[u].push_back(p(val,v));
        vec[v].push_back(p(val,u));
    }
    priority_queuevector
,greater
 >pq;
    vis[1] = 1;
    for(int i = 0;i 1].size();i++){
        pq.push(vec[1][i]);
    }
    int ans = 0;
    while(!pq.empty()){
        p now = pq.top();
        pq.pop();
        if(!vis[now.second]){
            vis[now.second] = 1;
            ans += now.first;
            for(int i = 0;i if(!vis[vec[now.second][i].second])
                    pq.push(vec[now.second][i]);
            }
        }
    }
    printf("%d\n",ans);
}