大佬们求助!!!全RE......

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

Jimmy1112 @ 2022-05-14 10:56:38

下面是我的代码,dijkstra+堆优化:

cpp
#include<bits/stdc++.h>
#define rg register int 
using namespace std;
int n,m,h[100011],sum=0,l=0,dis[100011],st,d;
bool bj[100011];
struct node
{
    int to,nxt,s;
}a[400011];
struct nood
{
    int zz,w;
}b[100011];
inline void add(int x,int y,int z)
{
    sum++;
    a[sum].to=y;
    a[sum].nxt=h[x];
    a[sum].s=z;
    h[x]=sum;
}
inline void put(int x,int y)
{
    int net,now;
    l++;
    b[l].zz=x;
    b[l].w=y;
    now=l;
    while(now>1)
    {
        net=now/2;
        if(b[net].zz>=b[now].zz) return ;
        swap(b[net],b[now]);
        now=net; 
    } 
}
inline nood get()
{
    int net,now=1;
    nood k=b[1];
    b[1]=b[l--];
    while(now*2<=l)
    {
        net=now*2;
        if(net<l&&b[net].zz<b[net+1].zz) net++;
        if(b[now].zz>=b[net].zz) break;
        swap(b[now],b[net]);
        now=net; 
    } 
    return k;
}
int main()
{
    scanf("%d%d%d",&n,&m,&st);
    for(rg i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z); 
    } 
    dis[st]=0;
    d=h[st];
    bj[st]=1;
    do
    {
        dis[a[d].to]=a[d].s;
        put(a[d].s,a[d].to);
        d=a[d].nxt; 
    }
    while(d!=0);
    for(rg i=1;i<n;i++)
    {
        nood q=get();
        bj[q.w]=1;
        d=h[q.w];
        do
        {
            if(dis[a[d].to]>q.zz+a[d].s) dis[a[d].to]=q.zz+a[d].s;
            d=a[d].nxt;
        } 
        while(d!=0); 
    }
    for(rg i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    } 
    return 0;
 } 

by a746 @ 2022-07-07 09:39:53

试试每个数组都翻个20倍大小?我设数据点上限+4会RE三个点

以及这是有向图应该不需要存两条边吧


by Jimmy1112 @ 2022-07-07 20:01:28

@a746 3Q!


|