为什么要这么写?

P3366 【模板】最小生成树

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


|