XHZnewlife @ 2024-11-21 20:48:31
本人对着自己代码看了半个小时没看出问题 一看题 是个无向图……
#include<bits/stdc++.h>
using namespace std;
struct edge{
int node,quan;
bool operator<(const edge& other)const{
return quan>other.quan;
}
};
int n,m,ans=0;
int flag[5005]={},num=1;
vector<edge> ed[5005];
priority_queue<edge> dcl;
int main(){
cin>>n>>m;
for(int i=0,u,v,w;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
ed[u].push_back({v,w});
ed[v].push_back({u,w});//记得加双向aaa
}
int start=1;
for(int i=0;i<ed[start].size();i++)dcl.push(ed[start][i]);
flag[start]=1;
while(!dcl.empty() and num<n){
if(flag[dcl.top().node]==1){
dcl.pop();
continue;
}
ans+=dcl.top().quan;
flag[dcl.top().node]=1;
num++;
int p=dcl.top().node;
dcl.pop();
for(int i=0;i<ed[p].size();i++)dcl.push(ed[p][i]);
}
if(num==n)cout<<ans;
else cout<<"orz";
return 0;
}
真是服了自己了