spfa与SLF和LLL（复习）

 

先上题目链接

emmm，以后写博客一定贴题目链接，提高食用效果。

最后贴代码

#include <bits/stdc++.h>
using namespace std;
const int mac=4e5+50;
int head[mac],vis[mac],dis[mac];
int n,m,num,i,j,t;
struct edge{
    int v,w,next;
}a[mac]; 
void sc(){
    int x,y,z;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&z);
        a[++num]=(edge){y,z,head[x]};
        head[x]=num;
        a[++num]=(edge){x,z,head[y]};//无向图 双向边，然后数组两倍边数 
        head[y]=num;
    }
}
void spfa(){
    memset(dis,0x3f, sizeof(dis));
    deque<int>q;
    q.push_back(1); 
    vis[1]=1; 
    dis[1]=0;
    while(!q.empty()){
        t=q.front();
        q.pop_front();
        vis[t]=0;
        for(j=head[t];j!=0;j=a[j].next){
            int v=a[j].v;
            if(dis[v]>dis[t]+a[j].w){
                dis[v]=dis[t]+a[j].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(dis[v]<=dis[q.front()])
                        q.push_front(v); 
                    else
                        q.push_back(v);  
                }
            }
        }
    }
    if(dis[n]!=0x3f3f3f3f)
        printf("%d
",dis[n]);
    else
        cout<<"qwb baka"<<endl;//1和n不连通  
}
void spfabest(){
    memset(dis, 0x3f, sizeof(dis));
    deque<int> q;
    q.push_back(1);
    vis[1] = 1;
    dis[1] = 0;
    int cnt = 1,sum=0;
    while (!q.empty()) 
    {
        t = q.front();
       // cout<<"t="<<t<<endl;
//        while (cnt*dis[t] > sum) 
//        {
//            q.pop_front();
//            q.push_back(t);
//            t = q.front();
//        }把这个LLL优化屏蔽掉就过了 
        while (cnt*dis[t] > sum) 
        {
            q.pop_front();
            q.push_back(t);
            t = q.front();
        }
        q.pop_front();
        cnt--;
        sum-=dis[t];
        vis[t] = 0;
        for(j=head[t];j!=0;j=a[j].next){
            //cout<<"j="<<j<<endl;
            int v=a[j].v;
            if(dis[v]>dis[t]+a[j].w){
                dis[v]=dis[t]+a[j].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(dis[v]<=dis[q.front()]){
                        q.push_front(v); 
                    }
                    else
                        q.push_back(v);  
                    sum += dis[v];
                       cnt++;
                }
            }
            //printf("sum=%d,cnt=%d
",sum,cnt);
        }
    }
    if(dis[n]!=0x3f3f3f3f)
        printf("%d
",dis[n]);
    else
        cout<<"qwb baka"<<endl;//1和n不连通  
}
int main(){
    sc();
    spfabest();
}