prim+优先队列，最后一个点t掉了，求调

julihui325 @ 2024-08-01 16:45:26

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
    int x=0;
    short f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}  

struct edge{
    int to,nxt,w;
}e[400010];
struct node{
    int id,dist;
    bool operator < (node x) const{
        return x.dist<dist;
    }
};
int head[200010],tot;
void add(int u,int v,int w){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    e[tot].w=w;
    head[u]=tot;
}
int n,m,dis[5010];
bool vis[5010];
priority_queue <node> q;
int main(){
    int u,v,w,cnt=0,ans=0;
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        u=read();
        v=read();
        w=read();
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=n;i++)
        dis[i]=0x3f3f3f3f;
    q.push((node){1,0});
    while(!q.empty()||cnt<n-1){
        node t=q.top();
        q.pop();
        u=t.id;
        if(vis[u])
            continue;
        vis[u]=1;
        ans+=t.dist;
        cnt++;
        for(v=head[u];v;v=e[v].nxt){
            if(e[v].w<dis[e[v].to]){
                dis[e[v].to]=e[v].w;
                q.push((node){e[v].to,e[v].w});             
            }
        }
    }
    if(cnt<n-1)
        printf("orz");
    else
        cout<<ans;
    return 0;
}

by jimmy0926 @ 2024-08-02 08:35:07

@julihui325 根据亲测，最后一个点构不成最小生成树的原因是遍历完所有的边后没有 n - 1 条。

by jimmy0926 @ 2024-08-02 08:46:24

@julihui325 下载数据得：

input:
5 6
1 2 3
2 3 4
3 1 4
4 5 6
5 4 6
1 3 5

output:
orz

your output:
【啥也没有】

result:
process exited after xxx seconds with return value 3221225477

所以是 RE。 你谷的评测机对 RE 不敏感 ，我还有 RE 变 TLE 的经历 。

by jimmy0926 @ 2024-08-02 08:47:08

谢谢关注

by jimmy0926 @ 2024-08-02 09:00:35

优先队列被取空了还在调用 q.top()。

贴一份修改过的代码：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
inline int read()
{
    int x = 0;
    short f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

struct edge {
    int to, nxt, w;
} e[400010];
struct node {
    int id, dist;
    bool operator < (node x) const
    {
        return x.dist < dist;
    }
};
int head[200010], tot;
void add(int u, int v, int w)
{
    e[++tot].to = v;
    e[tot].nxt = head[u];
    e[tot].w = w;
    head[u] = tot;
}
int n, m, dis[5010];
bool vis[5010];
priority_queue <node> q;
int main()
{
    int u, v, w, cnt = 0, ans = 0;
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        u = read();
        v = read();
        w = read();
        add(u, v, w);
        add(v, u, w);
    }
    for (int i = 2; i <= n; i++)        //关于你要从 1 开始赋初值
        dis[i] = 0x3f3f3f3f;
    q.push({1, 0});
    while (!q.empty() && cnt < n) {     //关于你用 || 操作符 且 cnt < n - 1
        node t = q.top();
        q.pop();
        u = t.id;
        if (vis[u])
            continue;
        vis[u] = 1;
        ans += t.dist;
        cnt++;
        for (v = head[u]; v; v = e[v].nxt) {
            if (e[v].w < dis[e[v].to]) {
                dis[e[v].to] = e[v].w;
                q.push({e[v].to, e[v].w});
            }
        }
    }
    if (cnt < n)                        //同上，居然 - 1
        printf("orz");
    else
        printf("%d", ans);
    return 0;
}
/*请注意细节*/

by jimmy0926 @ 2024-08-02 09:01:27

@julihui325

by julihui325 @ 2024-08-02 09:53:42

@jimmy0926 已过，您真是个好人啊（感慨脸，大佬们都是人帅心善的

by jimmy0926 @ 2024-08-02 10:01:33

不用谢。

不知道该不该说，蒟蒻昨天才学最小生成树，正好不熟悉 Prim，想练手，又不(lan)想(de)敲，结果看到讨论区 prim+优先队列，最后一个点t掉了，求调，然后就没有然后了。。。