初学Prim,WA了7个点,求调

P3366 【模板】最小生成树

GalwayGirl @ 2022-07-20 14:43:11

#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int> >q;
int n,m,c,dis[5100],head[5100],s;
long long ans;
bool flag[5100];
struct xzh
{
    int next,to,w;
}edge[410000];
void add(int u,int v,int w)
{
    c++;
    edge[c].next=head[u];
    edge[c].w=w;
    edge[c].to=v;
    head[u]=c;
}
int main()
{
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m;
    while(m--)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dis[1]=0;
    q.push(make_pair(0,1));
    flag[1]=true;
    while(!q.empty()&&s<n)
    {
        int u=q.top().second,d=-q.top().first;
        q.pop();
        ans+=d;
        for(int i=head[u];i;i=edge[i].next)
        {
            if(edge[i].w<dis[edge[i].to])
            {
                dis[edge[i].to]=edge[i].w;
                if(!flag[edge[i].to])
                {
                    s++;
                    flag[edge[i].to]=true;
                    q.push(make_pair(-dis[edge[i].to],edge[i].to));
                }
            }
        }
    }
    if(s==n-1)cout<<ans;
    else cout<<"orz";
    return 0;
}

by 李夹木 @ 2022-07-20 14:54:12

用kruskal(比Prim快,还好用)


|