thrX @ 2024-03-24 15:04:12
本来是不会改的,看了tj后改了一个符号,但是不李姐,求解答
#include<bits/stdc++.h>
#define inf 0xffffff
using namespace std;
int n,m,dst[5005],hd[5005],k,ans,tot;
bool vis[5005];
struct node{
int to,next,w;
}edge[400005];
struct p{
int id,d;
bool operator<(const p &a)const{
return a.d<d;
}
};
void adde(int u,int v,int w){
edge[++k].to=v;
edge[k].w=w;
edge[k].next=hd[u];
hd[u]=k;
}
void add(int u,int v,int w){
adde(u,v,w);
adde(v,u,w);
}
void prim(){
fill(dst+1,dst+1+n,inf);
priority_queue<p> q;
p now;
now.id=1,now.d=dst[1]=0;
q.push(now);
while(!q.empty()){
p now=q.top();
q.pop();
int u=now.id;
if(now.d!=dst[u])continue;
vis[u]=1;
ans+=dst[u];
tot++;
for(int i=hd[u];i;i=edge[i].next){
int v=edge[i].to;
if(!vis[v]&&dst[v]>edge[i].w){
dst[v]=edge[i].w;
p nt;
nt.d=dst[v];
nt.id=v;
q.push(nt);
}
}
}
if(tot<n)ans=-1;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
int u,v,w;
for(int i=0;i<m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
prim();
if(ans==-1)cout<<"orz"<<'\n';
else cout<<ans<<'\n';
return 0;
}
问题就是,为什么12行要用小于,按理来说不应该是大于号吗?只改了一个符号就AC了
by Weekoder @ 2024-03-24 15:11:23
@threeex_xyu 是小于号啊,不然就是最大生成树了
by thrX @ 2024-03-24 15:12:22
@Weekoder
明白了(大悟
谢谢julao