求救!! prim 44分 找不出哪里错了 , qwq 5555

P3366 【模板】最小生成树

VxiaohuanV @ 2021-11-17 19:31:00

#include <bits/stdc++.h>
using namespace std;
#define ri register int
#define M 5005

struct edge{
    int v,val;
    edge(){}
    edge(int a,int b){v=a,val=b;}
};
vector <edge> p[M];
int n,m;
long long  dis[M];
int val[M],vis[M];
struct cmp{
    bool operator ()(const int a,const int b)const
    {
        return val[a]>val[b];
    }
};
priority_queue <int,vector<int>,cmp> q;

long long ans;
bool flag;
int cent;
void dj()
{
    memset(val,0x3f,sizeof(val));   
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;val[1]=0;
    q.push(1);
    while(n--)
    {
        cent++;
        int a=1; // attention
        while(!q.empty())
        {
            a=q.top();
            if(vis[a]) q.pop();
            else break;
        }
        if(vis[a]) 
        {
            flag=1;break;
        };
        vis[a]=1;
        ans+=val[a];
        for(ri i=0;i<p[a].size();i++)
        {
            int b=p[a][i].v;
            if(vis[b]) continue;
            if(val[b]>p[a][i].val)
            {
                val[b]=p[a][i].val;q.push(b);
            }
        }   
    }   
}
int main(){

    scanf("%d%d",&n,&m);
    for(ri i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge t=edge(b,c);
        p[a].push_back(t);
        t=edge(a,c);
        p[b].push_back(t);
    }

    dj();

    if(flag) printf("orz");
    else
    printf("%lld",ans);

    return 0;
}

by XiaoQuQu @ 2021-11-19 10:00:17

@VxiaohuanV 额没看懂您的代码


|