32分超时求优化

P4779 【模板】单源最短路径(标准版)

xmbc @ 2024-01-19 17:35:23

#include<cstdio>
using namespace std;
struct
{
    int from,to,w,next;
}e[200001];
int h[100001],cnt=1,ans[100001],x[200001],y=1;
void add(int u,int v,int w)
{
    e[cnt].next=h[u];
    h[u]=cnt;
    e[cnt].from=u;
    e[cnt].to=v;
    e[cnt].w=w;
    cnt++;
}
void bfs()
{
    int i,z;
    for(i=0;i!=y;i=(i+1)%200001)
    {
        for(z=h[x[i]];z;z=e[z].next)
        {
            if(ans[e[z].to]>ans[e[z].from]+e[z].w)
            {
                ans[e[z].to]=ans[e[z].from]+e[z].w;
                x[y]=e[z].to;
                y=(y+1)%200001;
            }
        }
    }
}
void so(int u)
{
    int i,min,t;
    min=h[u];
    for(i=min;i;i=e[i].next)
        if(e[i].w<e[min].w)
            min=i;
    if(min!=h[u])
    {
        t=e[h[u]].from;
        e[h[u]].from=e[min].from;
        e[min].from=t;
        t=e[h[u]].to;
        e[h[u]].to=e[min].to;
        e[min].to=t;
        t=e[h[u]].w;
        e[h[u]].w=e[min].w;
        e[min].w=t;
    }
}
int main()
{
    int n,m,s,i,u,v,w;
    scanf("%d%d%d",&n,&m,&s);
    for(i=0;i<=100000;i++)
    {
        h[i]=0;
        ans[i]=0x7fffffff;
    }
    for(i=0;i<=200000;i++)
    {
        e[i].next=0;
        x[i]=0x7fffffff;
    }
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(i=1;i<=n;i++)
        so(h[i]);
    ans[s]=0;
    x[0]=s;
    bfs();
    for(i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

by OIer_bcx_ @ 2024-01-19 18:18:53

这题卡SPFA


|