SPFA及其优化---他复活了

SPFA算是一种比较万能的最短路算法了
时间复杂度:O(mn)
特点:
1.每个点可以入队多次
2.不能处理负环,但可以判断负环
3.队列优化减少一些冗余的松弛操作

贴一个模板题http://www.acmicpc.sdnu.edu.cn/problem/show/1223

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;

struct node
{
    int y,z,next;
}t[1000000];

int n,m,tot,a,b,c;
bool v[10000];
int d[10000],head[10000],times[10000];

void init()
{
    for(int i = 1;i <= n; ++i)
    {
        d[i] = 1e9;     //统计起点开始到各点的最短路径
        v[i] = 0;  //标记是否在队列中
        head[i] = -1;
        times[i] = 0;   //入队次数,用以判断负环
    }
}

void add(int x,int y,int z)
{
    t[++tot].y = y;
    t[tot].z = z;
    t[tot].next = head[x];
    head[x] = tot;
}

bool spfa(int start)
{
    queue<int>q;
    d[start] = 0;
    v[start] = 1;
    q.push(start);
    times[start] = 0;
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        v[now] = 0;    //记得把now的标记去掉才能再次入队
        for(int i = head[now];i != -1;i = t[i].next)
        {
            if(d[t[i].y] > d[now] + t[i].z)
            {
                d[t[i].y] = d[now] + t[i].z;
                if(!v[t[i].y])
                {
                    v[t[i].y] = 1;
                    q.push(t[i].y);
                    if(++times[t[i].y] > n) return 0;
                }
            }
        }
    }
    return 1;
}

int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        init();
        for(int i = 1;i <= m; ++i)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        if(spfa(1))printf("%d\n",d[n]);
        else printf("IMPOSSIBLE!\n");
    }
    return 0;
}

当然这只是朴素的SPFA,做题中有好多题是专门用来卡SPFA的(有点惨哦)
所以可以加优化
SLF 双端队列 极值优化:即将入队的点dist(i)若比队头元素dist(j)大,就从后面入队,否则从前面入队
LLF 平均值优化:队列中所有dist值的平均值为x,若即将入队的点dist(i)>x则将i插入到队尾,否则从前面入队
优先队列优化:每次入队都从小到大自动排序,看起来每次都选取最优的,但实际每次都要维护队列,也增加了一些不必要的操作,复杂度并不敢保证

还是这个题http://www.acmicpc.sdnu.edu.cn/problem/show/1223

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;

struct node
{
    int y,z,next;
}t[1000000];

int n,m,tot,a,b,c,sum,ts;
bool v[10000];
int d[10000],head[10000],times[10000];

void init()
{
    for(int i = 1;i <= n; ++i)
    {
        d[i] = 1e9;
        v[i] = 0;
        head[i] = -1;
        times[i] = 0;
    }
    sum = 0;
}

void add(int x,int y,int z)
{
    t[++tot].y = y;
    t[tot].z = z;
    t[tot].next = head[x];
    head[x] = tot;
}

bool spfa(int start)
{
    deque<int>q;
    d[start] = 0;
    v[start] = 1;
    q.push_front(start);
    times[start] = 0;
    sum += start; ts = 1;
    while(!q.empty())
    {
        int now = q.front();
        q.pop_front();
        v[now] = 0;
        sum -= d[now];
        ts--;
        for(int i = head[now];i != -1;i = t[i].next)
        {
            if(d[t[i].y] > d[now] + t[i].z)
            {
                d[t[i].y] = d[now] + t[i].z;
                if(!v[t[i].y])
                {
                    v[t[i].y] = 1;
                    if(q.empty() || d[t[i].y] > d[q.front()] || d[t[i].y] * ts > sum)  
                    	q.push_back(t[i].y);
                          //如果队列为空进行q.front()会出错
                    else
                        q.push_front(t[i].y);
                    sum += d[t[i].y];
                    if(++times[t[i].y] > n) return 0;
                }
            }
        }
    }
    return 1;
}

int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        init();
        for(int i = 1;i <= m; ++i)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        if(spfa(1))printf("%d\n",d[n]);
        else printf("IMPOSSIBLE!\n");
    }
    return 0;
}

http://blog.sina.com.cn/s/blog_6f6e97490100tlmj.html

全部评论

相关推荐

07-09 19:25
门头沟学院 Java
这是要把每一个投校招的都开盒吗?
26届之耻将大局逆转:裁人的时候一次性追回餐费
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 12:10
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务