Spfa + SLF&LLL优化

【Spfa + SLF&LLL优化】仰天大笑出门去，我辈岂是蓬蒿人。这篇文章主要讲述Spfa + SLF&LLL优化相关的知识，希望能为你提供帮助。
Spfa + SLF& LLL优化基本原理效率分析核心代码SLF

deque< ll> q;
void Spfa()

for(ll i=1; i< =n; i++)dis[i]=INF;
dis[s]=0;
q.push_back(s);
vis[s]=1;
while(!q.empty())

ll u=q.front();
q.pop_front();
vis[u]=0;
for(ll i=head[u]; i; i=edge[i].next)

ll v=edge[i].v,w=edge[i].w;
if(dis[v]> dis[u]+w)

dis[v]=dis[u]+w;
if(!vis[v])

if(dis[v]< =dis[q.front()])q.push_front(v);
else q.push_back(v);
vis[v]=1;

LLL

ll tot=1,sum;
queue< ll> q;
void Spfa()

for(ll i=1; i< =n; i++)dis[i]=INF;
dis[s]=0;
q.push(s);
vis[s]=1;
while(!q.empty())

ll u=q.front();
while(tot*dis[u]> sum)

q.pop();
q.push(u);
u=q.front();

q.pop();
tot--;
sum-=dis[u];
vis[u]=0;
for(ll i=head[u]; i; i=edge[i].next)

ll v=edge[i].v,w=edge[i].w;
if(dis[v]> dis[u]+w)

dis[v]=dis[u]+w;
if(!vis[v])

q.push(v);
vis[v]=1;
sum+=dis[v];
tot++;

SLF + LLL

ll tot=1,sum;
deque< ll> q;
void Spfa()

for(ll i=1; i< =n; i++)dis[i]=INF;
dis[s]=0;
q.push_back(s);
vis[s]=1;
while(!q.empty())

ll u=q.front();
while(tot*dis[u]> sum)

q.pop_front();
q.push_back(u);
u=q.front();

q.pop_front();
tot--;
sum-=dis[u];
vis[u]=0;
for(ll i=head[u]; i; i=edge[i].next)

ll v=edge[i].v,w=edge[i].w;
if(dis[v]> dis[u]+w)

dis[v]=dis[u]+w;
if(!vis[v])

if(q.size()& & dis[v]< =dis[q.front()])q.push_front(v);
else q.push_back(v);
vis[v]=1;
sum+=dis[v];
tot++;

例题解析??洛谷 P3371 【模板】单源最短路径（弱化版）??

#include
using namespace std;
typedef long long ll;
#define maxn 10005
#define maxm 500005
#define INF 2147483647
template< class T> inline bool read(T & x)

x=0; register char c=getchar(); register bool f=0;
while(!isdigit(c))if(c==EOF)return false; f^=c==-,c=getchar();
while(isdigit(c))x=(x< < 3)+(x< < 1)+(c^48),c=getchar();
if(f)x=-x;
return true;

template< class T> inline void print(T x)

if(x< 0)putchar(-),x=-x;
if(x> 9)print(x/10);
putchar(x%10^48);

template< class T> inline void print(T x,char c)print(x),putchar(c);
ll n,m,s,cnt,head[maxn],dis[maxn],tot=1,sum;
bool vis[maxn];
struct Edgell u,v,w,next; edge[maxm];
void add(ll u,ll v,ll w)

edge[++cnt].u=u;
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;

deque< ll> q;
void Spfa()

for(ll i=1; i< =n; i++)dis[i]=INF;
dis[s]=0;
q.push_back(s);
vis[s]=1;
while(!q.empty())

ll u=q.front();
while(tot*dis[u]> sum)

q.pop_front();
q.push_back(u);
u=q.front();

q.pop_front();
tot--;
sum-=dis[u];
vis[u]=0;
for(ll i=head[u]; i; i=edge[i].next)

ll v=edge[i].v,w=edge[i].w;
if(dis[v]> dis[u]+w)

dis[v]=dis[u]+w;
if(!vis[v])

if(q.size()& & dis[v]< =dis[q.front()])q.push_front(v);
else q.push_back(v);
vis[v]=1;
sum+=dis[v];
tot++;

int main()

read(n),read(m),read(s);
ll u,v,w;
for(ll i=1; i< =m; i++)

read(u),read(v),read(w);
add(u,v,w);

Spfa();
for(ll i=1; i< =n; i++)print(dis[i], );
return 0;