警钟长鸣!(如果只有最后一点通过)

P3366 【模板】最小生成树

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;
}

真是服了自己了


|