1 solutions

  • 0
    @ 2022-6-1 17:51:53
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll cet,dis[310000],head[310000],n,m,cnt,x,y,z,sum;
    struct edge{
    	ll next,to,val;
    }e[5100000];
    bool vis[310000];
    void add(int u,int v,int w){//添加节点
    	e[++cet].next=head[u];
    	head[u]=cet;
    	e[cet].to=v;
    	e[cet].val=w;
    }
    typedef pair<ll,ll>pii;//《权值,节点》
    priority_queue<pii,vector<pii>,greater<pii> >q;
    void prime(){
    	dis[1]=0;
    	q.push(make_pair(0,1));
    	while(!q.empty()){
    		ll d=q.top().first,u=q.top().second;
    		q.pop();
    		if(vis[u]) continue;
    		sum+=d;
    		vis[u]=1;
    		for(int i=head[u];i!=0;i=e[i].next){//更新
    			if(dis[e[i].to]>e[i].val){
    				dis[e[i].to]=e[i].val,q.push(make_pair(dis[e[i].to],e[i].to));
    			}
    		}
    		
    	}
    }
    int main(){
    	memset(dis,127,sizeof(dis));//无穷大
    	scanf("%lld%lld",&n,&m);
    	for(int i=0;i<m;i++){
    		scanf("%lld%lld%lld",&x,&y,&z);
    		add(x,y,z);add(y,x,z);
    	}
    	prime();
    	printf("%lld",sum);
    	//else printf("orz");
    	return 0;
    }
    

    Information

    ID
    70
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    # Submissions
    14
    Accepted
    3
    Uploaded By