SPFA,它……真的死了吗?

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

cold_dzy_light @ 2024-10-22 22:31:42

#include<bits/stdc++.h>
#pragma G++ optimize(1,2,3,"Ofast","inline","-fgcse","-fgcse-lm","-fipa-sra","-ftree-pre","-ftree-vrp","-fpeephole2","-ffast-math","-fsched-spec","unroll-loops","-falign-jumps","-falign-loops","-falign-labels","-fdevirtualize","-fcaller-saves","-fcrossjumping","-fthread-jumps","-funroll-loops","-fwhole-program","-freorder-blocks","-fschedule-insns","inline-functions","-ftree-tail-merge","-fschedule-insns2","-fstrict-aliasing","-fstrict-overflow","-falign-functions","-fcse-skip-blocks","-fcse-follow-jumps","-fsched-interblock","-fpartial-inlining","no-stack-protector","-freorder-functions","-findirect-inlining","-fhoist-adjacent-loads","-frerun-cse-after-loop","inline-small-functions","-finline-small-functions","-ftree-switch-conversion","-foptimize-sibling-calls","-fexpensive-optimizations","-funsafe-loop-optimizations","inline-functions-called-once","-fdelete-null-pointer-checks")
using namespace std;

#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1000000,stdin)), p1==p2 ? EOF : *p1++)
char buf[1000000], *p1 = buf, *p2 = buf;
inline const void read(int &a){ register char ch=getchar();bool f=false;a=0;while(ch<'0'||ch>'9')ch=='-'&&(f=true),ch=getchar();while(ch<='9'&&ch>='0')a=(a<<1)+(a<<3)+(ch^48),ch=getchar();f&&(a=-a); }

vector <pair<int,int> >mp[100010];

int d[100200];
bool vis[100200];
int n,m,k,s;
list <int>q;
bool cmp(int a,int b)
{
    return d[a]<d[b];
}
int main()
{
    srand(time(0));
    read(n),read(m),read(s);
    int v,x,y,z;
    for(register int i = 1;i <= m; ++i) {
        read(x),read(y),read(z); 
        mp[x].push_back(make_pair(y,z));
    }
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    vis[s]=1;
    q.push_back(s);
    for(;!q.empty();)
    {
        if(rand()%((q.size()>>2+1>>3)+1)==0)
        {
            q.sort(cmp);
        }
        int x=q.front();
        q.pop_front();
        vis[x]=0;
        for(register int i=0;i<mp[x].size();i++)
        {
            int p=mp[x][i].first;
            int lp=mp[x][i].second;
            if(d[x]+lp<d[p])
            {
                d[p]=d[x]+lp;
                if(!vis[p]) 
                {
                    if(d[p]>d[q.front()])q.push_back(p);
                    else q.push_front(p);
                    vis[p]=1;
                }
            }
        }
    }
    for(register int i=1;i<=n;i++)
    {
        cout<<d[i]<<' ';
    }
    return 0;
}

80分大佬帮帮忙


by LLVM_lldb_14_0_0 @ 2024-10-22 22:37:33

@cold_dzy_light 应该死了


by LLVM_lldb_14_0_0 @ 2024-10-22 22:38:01

或者是我太菜了


by ikunTLE @ 2024-10-22 22:40:00

@cold_dzy_light 去弱化版就活了


by InterN_NOT_FOUND @ 2024-10-22 22:44:23

真似了,但是可以试试玄学优化


by rnf5114 @ 2024-10-22 22:56:02

@cold_dzy_light nsdd但是dij堆优化不比这好些多了


by zhuoheng @ 2024-10-25 20:12:25

@rnf5114 实际赛场上我觉得不如spfa,比spfa难打不说还不定比spfa快除非出题人没良心


by Mugino_Shizuri @ 2024-10-26 08:46:36

@zhuoheng 不卡 SPFA 才叫没有良心。


|