52分求调

llll123321 @ 2024-10-08 17:28:58

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,M=2e5+1;
struct edge 
{
    int u,v,n,w;
}e[M];
int fl[N],head[N];
int n,m,dis[N],s,cnt=0;
struct point 
{
    int p,dis;
    bool operator < (point x)const{return dis>x.dis;}
};
priority_queue<point> q;
inline int read() 
{
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void dij()
{
    dis[s]=0;
    q.push((point){s,dis[s]});
    while(!q.empty())
    {
        int top=q.top().p;
        q.pop();
        for(int i=head[top];i;i=e[i].n)
        {
            if(dis[e[i].v]>dis[top]+e[i].w)
            {
                dis[e[i].v]=dis[top]+e[i].w;
                if(fl[e[i].v]==0) {fl[e[i].v]=1;q.push((point){e[i].v,dis[e[i].v]});}
            }
        }
    }
}
int main()
{
    memset(fl,0,sizeof(fl)); memset(head,0,sizeof(head));  memset(dis,0x6f,sizeof(dis));
    n=read();m=read();s=read();
    cerr<<n<<m<<s;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        e[++cnt]=(edge){u,v,head[u],w};
        head[u]=cnt;
    }
    fl[s]=1;
    dij();
    for(int i=1;i<=n;i++)cout<<dis[i]  <<" ";
    return 0;
}

by Lu_xZ @ 2024-10-08 17:41:19

@llll123321 fl 数组用错了。

可能 dis[e[i].v] 会被当前层的其他点更新成更小的值，但是不会被你 push 到 pq 里，导致堆顶不是当前最小值，整个算法出现错误。

by WangSiHan_2011 @ 2024-10-08 17:41:59

AC:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,M=2e5+1;
struct edge 
{
    int u,v,n,w;
}e[M];
int fl[N],head[N];
int n,m,dis[N],s,cnt=0;
struct point 
{
    int p,dis;
    bool operator < (point x)const{return dis>x.dis;}
};
priority_queue<point> q;
inline int read() 
{
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void dij()
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push((point){s,dis[s]});
    while(!q.empty())
    {
        int top=q.top().p;
        q.pop();
        if(fl[top])
            continue;
            fl[top] = 1;
        for(int i=head[top];i;i=e[i].n)
        {
            if(dis[e[i].v]>dis[top]+e[i].w)
            {
                dis[e[i].v]=dis[top]+e[i].w;
                if(fl[e[i].v]==0) {q.push((point){e[i].v,dis[e[i].v]});}
            }
        }
    }
}
int main()
{
    memset(fl,0,sizeof(fl)); memset(head,0,sizeof(head));  memset(dis,0x6f,sizeof(dis));
    n=read();m=read();s=read();
    cerr<<n<<m<<s;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        e[++cnt]=(edge){u,v,head[u],w};
        head[u]=cnt;
    }
    dij();
    for(int i=1;i<=n;i++)cout<<dis[i]  <<" ";
    return 0;
}

by llll123321 @ 2024-10-08 18:59:18

@Lu_xZ @SDSZ_WangSiHan_2011 谢谢AC了