算法求助

yfjhhh

求助，自己写的一个最小生成树代码，AC不了
洛谷题目
代码如下：

#include<bits/stdc++.h>
using namespace std;
struct edge{ //定义边
        int value;//权值
        int spot;//到达点
};
bool spot[100];//点是否经过
struct cmp {
        bool operator() (edge& a,edge& b) {
                // 定义优先级的比较方式
                return a.value < a.value;
        }
};
priority_queue<edge, vector<edge>, cmp> pq;
int main()
{
        int map[100][100];
        edge e;
        memset(map,-1,sizeof(map));
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=m;i++){
                int x,y,z;
                cin>>x>>y>>z;
                map[x][y]=z;
                map[y][x]=z;
                //cout<<z<<endl;
        }
        int begin=1,l=0,ans=0;
        do{
                //cout<<111<<endl;
                for(int i=1;i<=n;i++){
                        //cout<<"test1:"<<i<<endl;
                        if(map[begin][i]!=-1&&spot[i]==0){
                                e.spot=i;
                                e.value=map[begin][i];
                                pq.push(e);
                                //cout<<"test2:"<<begin<<"to"<<e.spot<<endl;
                        }
                }
                spot[begin]=1;
                if(!pq.empty()&&l<=n-2){
                        edge eee;
                        eee=pq.top();
                        ans+=eee.value;
                        begin=eee.spot;
                        l++;
                        //cout<<"test3:"<<ans<<endl;
                        pq.pop();
                }
                else 
                {
                        break;
                }
        }while(1);
        //cout<<ans<<endl;
        //cout<<l<<endl;
        //cout<<l<<endl<<n;
        if(l==n-1){
                cout<<ans;
        }
        else
        {
                cout<<"orz";
        }
}

yfjhhh

链接https://www.luogu.com.cn/problem/P3366#submit

TenSir152

我先去实验一下

400h297004533

#include<bits/stdc++.h>
using namespace std;

struct edge {
    int value; // 权值
    int spot;  // 到达点
};

bool spot[100];  // 点是否经过

struct cmp {
    bool operator() (edge& a, edge& b) {
        // 定义优先级的比较方式
        return a.value < b.value;
    }
};

priority_queue<edge, vector<edge>, cmp> pq;

int main() {
    int map[100][100];
    edge e;
    memset(map, 0, sizeof(map));
   
    int n, m;
    cin >> n >> m;
   
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        map[x][y] = z;
        map[y][x] = z;
    }
   
    int begin = 1, l = 0, ans = 0;
   
    do {
        for (int i = 1; i <= n; i++) {
            if (map[begin][i] != 0 && spot[i] == 0) {
                e.spot = i;
                e.value = map[begin][i];
                pq.push(e);
            }
        }
        
        spot[begin] = 1;
        
        if (!pq.empty() && l <= n - 2) {
            edge eee = pq.top();
            ans += eee.value;
            begin = eee.spot;
            l++;
            pq.pop();
        } else {
            break;
        }
    } while (1);
   
    if (l == n - 1 && pq.empty()) {
        cout << ans;
    } else {
        cout << "orz";
    }
   
    return 0;
}