知识点汇总（希望置顶）

退站声明

相信大家也都是看到标题进来的，有些人可能会问，“唉？是不是在开玩笑啊？” 但是，我是真的要退了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1.回忆录 我在2020/11/5 加入了小码王scratch编程社区，那是一个和谐又不和谐的社区（？），至于我是怎么知道的，我自己也不记得了。 2022/12/25 我加入了小码王旗下的C++编程社区----ACGO，刚入站的我就创立了“中国”团队 2023/09 我在小码王scratch编程社区获得了“风纪委员”的称号 2023/10 我参加了我第一次排位赛，获得了第25名的成绩 2023/12 我创办了ACGO第一次非官方团队邀请赛，有非常多的人参与 2023/11-2024/07 我陆续参加了数十次官方比赛，并在排位赛#10后获得了全站第一的排名 2023/12 我开始写数学、智力游戏技巧等帖子，获得精选 2024/01 我开始写排位赛、欢乐赛等官方比赛的题解，获得精选 2024/02 在这之后，我开始写一些娱乐帖子，并开始曝光一些人的违规、不当事迹 2024/04 陈臻武事件爆发，我曝光了陈臻武多次，并使陈臻武获得了30天的小黑屋 2024/04 在这之后，不断有不当事迹被我曝光，我也收到了某些人的不满，于是我停止曝光举报他人 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2.一些问题 很多人都问过我，我是男的女的？我几岁？哪个学校？这并不重要吧。 也有人质疑，“一只姜不是小码王学员吗？”，这里我统一回复，我并不是小码王学员，只是一个外来人员罢了 如果有人想要知道我对TA的印象，可以在评论区打出“印象” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3.一些事迹 picture: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4.关于团队 我创办的“中国”团队在2022/12建立以后不断扩大，现在已有205人了，并且具有大量的大佬 在我退站后，“中国”团队将由SJZ08和Macw07接管 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我将在2024年的CSP-J/S结束后退站，会再发一个帖子，有什么问题评论区也可以提出，谢谢

天目山八月二期十日游记#集训营日记#

总是忘记改这个破计时器 离出营地还有3天? 早！就！出！狱！了！ 房顶上已经有我的 12 架纸飞机了(教室对面的房顶，宿舍和食堂楼) 八月19日晚上8:24补充，加上引用会不会让阅读体验舒服点? 已经无聊到写游戏了……,这么小应该绝对没人能看到吧\tiny 已经无聊到写游戏了……,这么小应该绝对没人能看到吧已经无聊到写游戏了……,这么小应该绝对没人能看到吧 诶嘿 是谁不点赞，你这样暴力是会TLE的(#>Д<)ﾉ 八月11日 DAY1DAY1DAY1 * 已经过十天的老登的教室从一楼换到了二楼 * 寝室从三楼换到了二楼 * 为什么！我们这些老登要去开营仪式，上一届不需要，这不公*！！！ * 目前一切正常，但是感觉老师一届比一届严? 奇奇怪怪的(除了睡觉居然不让关门?) * 没什么想写的 一会再说吧 * 突然想起来了，纪念Macw离开天目山第一天 八月12日 DAY2DAY2DAY2 * 纪念Macw离开天目山第二天 * 室友和我没什么共同语言，感觉后十天比较难熬a * 上午讲的哈希？感觉易如反掌 * 讲到字符串了，打代码了，老实了，难( * 主讲老师还是比较幽默的(我当然不是说张老师和唐老师不好) * 下午又没听课，x03遗留的传统(我是蒟蒻) * 考试据Macw评价说考的不错(大喜) > > ↑也算是开了个好头↑↑也算是开了个好头↑ ↑也算是开了个好头↑ * 今天突然49条回复，那不是持续三天就上热门了 八月13日 DAY3DAY3DAY3 * 虽然今天是12日，但是纪念Macw离开第三天，永远缅怀怀念Macw在山上的日子www * 11天(加上去年20天)的老登一针见血：早饭一点能吃的都没(应该没有老师会看到吧) * 现在是13日了，永远缅怀怀念Macw在山上的日子 * 昨天晚上眼镜框断了，上午变瞎子了，近视400度真的难受，电脑屏幕都看不清更别说看老师讲课了 * 一上午没听课，感觉自己变废柴了 * 中午有人老是叫，五子棋一把没赢过(感觉眼睛没了反而不会看不见别人的活三了?) * 一下午没刷题，等待着我的眼镜，真的要变成瞎子了，绝对不是我懒找的借口 * 本来以为我刷到day4已经够快了，没想到我室友已经刷到day5了，决定直接开摆了 * 寝室目前Macw留的遗产没剩多少了，悲 so aad * 今晚初赛考废了，寄 八月14日 DAY4DAY4DAY4 * 纪念Macw离开第四天，永远缅怀怀念Macw在山上的日子www * 讲的最短路，可惜我已经学过了(Macw锐评我的dijkstra：你这个写法属于是dij优化和spfa的粘合体) > * 欢乐赛开始了，准备先去看看(绝对不是懒的做团队的作业) * ? 我怎么记得有个欢乐赛来着，我失忆了?!?! * 舒服 已经到day6的练习了 (中间空了几题不会的) * 声讨acgo取消的欢乐赛，我只能去写作业，让我的大脑旋转 飞起来！ * 第二次的考试考炸了 > 八月15日 DAY5DAY5DAY5 * 纪念Macw离开第五天，永远缅怀怀念Macw在山上的日子www * 昨晚上彻底社死 > * 不是哥们你也没说你是女的啊，我去找你开门的时候给我吓飞了 (然后飞速逃逸) * AK了欢乐赛 真好 > * 夏老师又开始欠课了(讲的有点慢拖欠知识点) * 今天也没什么能写的，过了过了 八月16日 DAY6DAY6DAY6 * 纪念Macw离开第六天，永远缅怀怀念Macw在山上的日子www * 昨天晚上初赛感觉又炸了，到底是谁想出来专题卷这种恶心东西( * 起晚了，集合的时候才被叫醒，感觉最近一天起的比一天晚。 * 中午和笨比室友玩狼人杀，大聪明遥遥领先，第一天带节奏把预言家(我)投出去了 十分无语( * 夏老师上课出现名场面，（看看倒数第一的代码，___(Macw)没交 看不了） * 晚上和笨比队友玩扑克牌，我出完一张二就剩一张牌了，大聪明还是遥遥领先，直接大王把我压死，然后一张三送走地主，包会玩的( 八月17日 DAY7DAY7DAY7 * 纪念Macw离开第七天，永远缅怀怀念Macw在山上的日子www * 今天可是Macw的头七 都给我悲伤(bushi > * 捉一只发现自己被挂上去的Macw07 > * 大聪明遥遥领先，直接把房卡锁进了门里，永远纪念传奇开门王(bushi * 突然发现日记都写到Day7Day7Day7了 上面还是离出营地6天发现时间过的也挺快的(已改) * 发现LaTex文体真的好看，就是太细了发现LaTex文体真的好看，就是太细了发现LaTex文体真的好看，就是太细了 * 夏老师考试的时候突然生气了(可能是我们都要提前交卷)，害怕.ing * 别惦记你那个破链表了，蒟蒻真的没学过啊啊啊啊(未来人补充，链表我蒙的全对) * 有人说自己八点起床，可是八点半才起 (绝对不是尊贵的Macw大佬) 8月18日 DAY8DAY8DAY8 * 今天玩三国杀，造的时候宿舍突现北京文盲，乐 没错，还是这位大聪明，经典常谈之(赵、忠、贼、奸)怎么写，还有《操曹》 * 今天玩三国杀，突然又发现了北京老千，乐 啊对对对，还是这位大聪明，甄姬发洛神的时候偷偷把红色判定牌塞排堆底 包会出老千的啊，然后造报应被四个人集火了 哈哈哈哈哈哈 * 致敬传奇主公wyz，第二轮就把传奇忠臣大聪明秒杀了，可惜我开始认错队友了，不然这把直接天胡CCC位 忘记贴成绩了 > 8月19日 DAY9DAY9DAY9 * 三国杀开局摸了四张装备牌(两张马一张贯石斧一张八卦阵)有趣 然后就被后面的内奸拆完了，我发现某些人一直是内奸，基本都没换过 * 无敌了，到底是那个天才发明的口腔溃疡，已经不想活了 * WOC 我！被！置！顶！了！ * 无敌了 到底是谁把我生日传出去的，这个生日会真的尬的要死，已经要用脚趾抠出广搜模版了 > > 草忘记给Macw点赞了(已经点上了)草忘记给Macw点赞了(已经点上了) 草忘记给Macw点赞了(已经点上了) * 别问我为什么不回评论生日祝福的人，因为基本全是同班的 * 生日会晚上夏老师给我拉了托大的，晚上不让走给我放SEEYOUAGAIN,不是哥们你真的是牛逼 * 好，还不止SEEYOUAGAIN，还有生日快乐歌(海底捞版)不是哥们 * 一会真要脚抠DIJKSTRA了 8月20号 DAY10DAY10DAY10 * 今天早上一看，多了十几条信息，全是一个叫 . 的人点的，有趣 * 打表真的快乐，T8传家宝代码long long dp[]={0,1,0,1,0,1,0,1,0,1,0,1,2,3,5,8,13,21,34,55,89,144,0,3,0,11,0,41,0,153,0,571,0,1,5,11,36,95,281,781,2245,6336,18061,51205,0,8,0,95,0,1183,0,14824,0,185921,0,1,13,41,281,1183,6728,31529,167089,817991,4213133,21001799,0,21,0,781,0,31529,0,1292697,0,53175517,0,1,34,153,2245,14824,167089,1292697,12988816,108435745,1031151241,8940739824,0,55,0,6336,0,817991,0,108435745,0,14479521761,0,1,89,571,18061,185921,4213133,53175517,1031151241,14479521761,258584046368,3852472573499,0,144,0,51205,0,21001799,0,8940739824,0,3852472573499,0}; * Macw被迫加强了四次数据 有趣 * 讨厌acgo的讨论区机制，终于知道为什么Macw不爱回复信息了，因为根本找不到 回复多了后跳转不到评论里，需要自己手翻(恼 > 还怪巧的，第二名和我只差一点，居然也是222寝室的还怪巧的，第二名和我只差一点，居然也是222寝室的 还怪巧的，第二名和我只差一点，居然也是222寝室的 * 感谢一手大家 * 最后一天考试要考崩了，最后一题根本看不懂

曝光“LSQS”理事会！

“LSQS”理事会是杭州天目山营X01-2班的 陈*民 组建的团队，团队标题“LSQS" 其中包含辱骂老师的敏感词汇，建议删帖，散团。

200人的团踢一半了😢，求支持！！！

先看图 作为团队的队长，相信许多人也是感同身受的，曾经我的团队也有类似的情况，但是管理员也没有如此猖狂，这次直接踢一半，那位管理员的手估计都快残了，虽说目前查不出来，也没必要这样吧，我惹谁了吗？？？彼此之间按这点信任也没了...... 还是希望大家支持一下，被踢的拜托加回来，希望得到大家的支持，谢谢！！ 链接链接链接 这是目前管理员的名单： 昵称 职位 复仇者_林克━╋══⁕═➢™ 题库管理员、题单管理员、作业管理员、竞赛管理员 苍蓝残响* 管理员 AC神* 管理员 复仇者 管理员 奇点 管理员 北辞 管理员 李总 管理员 傲世万物* 管理员 带"*"号的为新增管理员 以上表格内的管理员都有嫌疑，我没有针对任何人，也没有一口咬定是谁，希望大家理解！！ 目前，我不会信任任何一个人，所以将现在的管理员暂时全部变成成员，希望大家理解！！！

关于某些胡说八道的人

首先，在2023.5这个账号才归我用，并且仍有2个拥有者，只是基本我用罢了 其次，当时在小码王的名字、假照片都是2022爆出来的，和我有什么关系吗 反正重点就是2023.5这个账号才是我用，账号名也不是我取的 而且男女有什么意义吗，我是女的我就不能加入ACGO？我是男的我就不能比赛？

#集训营日记#天目山集中营-连报

8.1~8.11：第一期就这么过去了。期间没记录什么。 8.11：第一批室友走了。 第一期概括： 主讲：重生之我是菜狗（蔡新宇老师）外号菜狗 助教：程怡老师（希望没写错） 大事祭：残忍杀死小强。 8.11~8.13： 8.11： 下午1:00至3:30。我们在教室玩了一下午的电脑。 下午3:30至5:00。找到新宿舍203，整个下午游戏玩齐了。 晚上：第二遍的开营仪式，我们宿舍合力收集了两百多张AC魔盒的卡片，用途结营后公布。 8.12 昨天开营仪式真的比第一次无趣多了，宿舍自我介绍都是老师一个一个宿舍点名上去的。 午餐感觉是一期二期目前有史以来最难吃的一次。 今天也是查看了军火库，目前军火：牛奶12瓶，梨子五个，香蕉2个，发糕四块 晚上第一次考试，竟然有AK的，震惊。本人样例都过，结果都错，8题错2。 九点多我们宿舍的典狱长（周**）四个梨子全干了 8.13 早上没晨跑，开心。 7:45：早餐水饺被弄没了 （我们宿舍一个人跟老师聊天聊着插队到了第一个） 总计军火库储备量：牛奶9，桃子5，香蕉10（可恶的典狱长晚上玩的时候吃了6根，看他不便秘） 典狱长ZZH战绩：三天不洗澡（每天下课还打羽毛球） 乐点：典狱长只有名义，方便称呼他，实力倒数第一 8.14 早上也没晨跑，开心 7:45：早餐第一次（个人）看见了小笼包，这是第二次好吃的早餐 上午上课，老师讲的真的好慢 中午回去，午餐一般 下午上课，第一节课昏昏欲睡，全程将知识点不让写代码，提不起精神 课间休息：晚点了。我们比别人晚下课却比别人早上课，离谱。 插播：羽毛球虐杀典狱长 第二节课还行，除了讲的慢没啥了 晚餐很好，偷偷弄了点军火 军火库：8牛奶（公用），3牛奶（我个人），12桃子，二十多葡萄（趁典狱长洗衣服我一个人吃完了），我和典狱长共偷渡了11虾棒，还找菜狗老师“乞讨”了两根 晚上18:30：写下今天的日记 待会要考试了…… > 20:20：这题目难爆了，肯定会超时，这要有人能AK必须膜拜 8.15 > 大事祭：菜狗成为主讲 没下雨，晨跑了 昨晚比赛真有人AK。。还是两个。。无语ing 今天评选流动红旗，本来打算中午弄，等一个人，结果等着等着忘了，估计我们宿舍最差。 希望能是脏乱宿舍中较干净的（我看对面也很乱） 下课打羽毛球，野孩子（不是诋毁，称呼）们玩一种乱七八糟的游戏，到处泼水，全湿了 （后面发现是泼水取乒乓球） 今天军火库战绩：21桃子！10+牛奶，20+葡萄（又被我独吞） 今晚两个人生日，真有趣，蹭了顿蛋糕，只是没什么时间写日记了 今晚初赛测试废了……………………………………………… > 补记：菜狗老师残忍砂*未知生物（类似小强） > 山上生物真多，有时候也有坏处，蜘蛛从空降落 8.16 第一次生病——肚纸好痛awa 我和室友联合怀疑食堂饭菜有问题 每次吃完都肚子痛 菜狗竟然洗头了 早饭我带走了唯一的水饺，油条是真的好吃，可惜那时候以为太硬了不好吃没带多几个 中午午饭还行，奶黄包 今天上课第一次全程没打瞌睡 通报：菜老师是个宅男！都不用动，叫他打羽毛球都不下来 老师放飞飞机，童心不改（返老还童不合适吧） 今晚复赛考试要是有AK我吃了。 蒟蒻只会3.5题awa 8.17 昨天半夜宿舍发生了一起案件。。。（很恐怖，结营再说吧） 昨晚的事，凌晨发生，今天下午第一节课昏昏欲睡awa 今天学习了动态规划，原来的递归递推基本都是超时，又是新知识 晚上又是初赛，紧张ing 食堂绝对有问题好吧，好多人肚子痛了。 今天又**了 > 大事祭：典狱长从开营到现在没洗过澡（6天） OK啊今天晚上的测试也是达到历史最高，在我们省直接过 8.18 今天头好晕，整个人都是迷茫的，就像行尸走肉。 是我被异化了吗？还是…… 17：17分：前排桌子瘫了，幸好电脑没逝（笑不活了 18：00：今天难怪头晕，发烧了……39°，我室友完蛋了……嘿嘿 坚持晚上来考试！ 8.19 > 超级新闻：典狱长8天不洗澡、五天才换+洗一次内裤！ 今天温度37了，还是有点晕，但是仍然坚持上课！ 肚子痛了，晚上考初赛模拟，一向是我不擅长的 8.20 昨晚去医院了。9：20出发，12：07才回来。 弄了两盒药回来； 今天下午学了树和表达式 马上刑满释放！ 8.21 > 八一集中营有感（没事干写的，很低级） > 题不在多，计算则烦 > 码不在长，递归/推则难 > 斯是OI，唯吾摆烂 > WA满江红，AC红绿灯 > 谈笑有巨佬，往来无蒟蒻 > 可以调代码，翻讨论。 > 贪心过样例，骗分TLE。暴力还CE。 > 小码**云：何AK之有 > 还有1天刑满释放awa

正式退站

昨天发的帖子违规被AC君删了. 今天重发一遍. 现在，2024/8/23，正式退站，别问我为什么提早.

OMG今天是七夕？？！！

废了废了

Dev-C++ 脱胎换骨の方法

前言 > 本文将介绍，在 Windows\tt{Windows}Windows 平台下，如何将本地IDE： Dev-C++ 的编译器升级，使得其能够支持 C++14 后的新特性，让使用了新特性的代码，在 Dev-C++ 上也能够编译通过。 现版本的 Dev-C++ 使用的 gcc\tt{gcc}gcc 版本比较低，一般为 gcc 4.9.2\tt{gcc\ 4.9.2}gcc 4.9.2，这使得一些使用新标准的 C++ 特性的代码无法通过编译，如图： 此代码使用了 C++17 加入的核心功能特性：结构化绑定(structured binding)[1]。 此次特性需要 gcc\tt{gcc}gcc 版本至少为 gcc 7.0.0\tt{gcc\ 7.0.0}gcc 7.0.0 及以上才能够支持[2]，所以这里使用 Dec-C++ 自带的 gcc 4.9.2\tt{gcc\ 4.9.2}gcc 4.9.2 无法编译此代码。 然而此特性非常重要，极大的方便了诸如 std::pair，std::map 等容器的访问与遍历，且虽然此特性为 C++17 的特性，但是可以在 gcc 7.0.0\tt{gcc\ 7.0.0}gcc 7.0.0 及以上通过编译，即使使用的命令行参数为 -std=c++14。 在目前的 CSP-J/S 中，编译选项为 -O2 -std=c++14 -static。且 CCF 目前评测机 NOI Linux 2.0\tt{NOI\ Linux\ 2.0}NOI Linux 2.0 使用的编译器为 gcc 9.3.0\tt{gcc\ 9.3.0}gcc 9.3.0[3]，所以此特性 可以在 CSP-J/S 中使用。 在 Acgo\tt{Acgo}Acgo 平台上所使用的编译器版本为 gcc 7.5.0\tt{gcc\ 7.5.0}gcc 7.5.0，所以此特性可以在 Acgo\tt{Acgo}Acgo 上使用。 另外，目前主流的竞赛平台和OJ都已经支持到了 C++20 或 C++23。 所以，给本地的 Dec-C++ 升级，使得其能够支持这些特性，就显得比较重要。 下载最新 GCC 14.2.0 我们可以在 winlibs 上，下载到 Windows\tt{Windows}Windows 平台下，最新版本的 gcc\tt{gcc}gcc 编译器。 这里可以下载到最新的 gcc 14.2.0\tt{gcc\ 14.2.0}gcc 14.2.0，若为 646464 位操作系统，选择 Win64\tt{Win64}Win64 否则选择 Win32\tt{Win32}Win32。 推荐选择 7-zip archieve 文件大小要比 Zip archieve 更小。 下载完毕后不要立即解压（下载后的压缩包大约为 158MB，但是解压后大小大约为 1.39GB，不方便移动）。推荐将下载后的压缩包放入 DDD 盘根目录下（若未分盘可选择 CCC 盘），然后使用解压软件，将其 「提取到当前位置」。 完成此步骤后，DDD 盘根目录下应有文件夹 mingw64，若为 winlibs-x86_64-posix-seh-gcc-14.2.0-llvm-18.1.8-mingw-w64ucrt-12.0.0-r1 则需要进入此文件夹，并将此文件夹下的 mingw64 移动到 DDD 盘根目录下即可。 配置 DEC-C++ 进入 Dec-C++ 选择 工具->编译选项。 选择第二个按钮 「添加新编译器设置」。 输入新编译器名称为 GCC 14.2.0。 接下来配置 「目录」 中的内容。 1. 添加二进制目录 在这里可以选择直接输入，或者通过文件夹选择。 按照以上步骤，解压的 mingw64 是在 DDD 盘根目录的话，这里的路径应为 D:\mingw64\bin。 输入或选择完毕后，点击 「添加」 即可。 2. 添加库目录 同上一步，在这里可以选择直接输入，或者通过文件夹选择。 按照以上步骤，这里的路径应为 D:\mingw64\lib。 输入或选择完毕后，点击 「添加」 即可。 3. 添加C包含文件目录 同上一步，在这里可以选择直接输入，或者通过文件夹选择。 按照以上步骤，这里的路径应为 D:\mingw64\include。 输入或选择完毕后，点击 添加 即可。 4. 添加C++包含文件目录 同上一步，在这里可以选择直接输入，或者通过文件夹选择。 按照以上步骤，这里的路径应为 D:\mingw64\include。 输入或选择完毕后，点击 「添加」 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 接下来配置 「程序」 中的内容。 这里按照下图，填写 gcc，g++，gdb 三项即可。 现在，我们便完成了所有配置。在这里选择刚刚配置的 GCC 14.2.0\tt{GCC\ 14.2.0}GCC 14.2.0。 现在，我们的 Dev-C++ 便可以通过开头的那段代码啦~ 设置编译选项 此时，如果想仿照考场上的编译选项，可以在 「编译器选项」 里设置。 勾选 「编译时加入以下命令」，并将 CSP-J/S 考试中给的编译选项 -O2 -std=c++14 -static 复制粘贴进去，就可以啦~ 至此，你的 Dec-C++ 便脱胎换骨，升级成功啦！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. C++ reference: Structured binding declaration ↩︎ 2. C++ reference: Compiler support for C++17 ↩︎ 3. CCF: NOI Linux 2.0发布，将于9月1日起正式启用！ ↩︎

图论续篇 - 最短路算法合集

> 我不会跟大家说我两个月前就写好了，只是今天才发出来。 本文概述 最短路算法，见名知意，就是用于求出图中从某个顶点到另一个顶点最短距离的算法。最短路算法的应用极其广泛。本文将会以求解最短路为中心，围绕着展开叙述一些常见的最短路算法的原理和应用。 根据最短路算法，我们大致地可以将算法分为两大类： 1. 单源最短路径 Single Source Shortest Path：用于快速计算从某一个特定顶点出发到达任意一个点的距离。 2. 多源最短路径 Multiple Source Shortest Path：用于快速计算任意两点之间的最短路径。 本文将会介绍的算法和各算法的特点如下： 1. 深度优先搜索 Depth First Search：单源最短路径算法，可以求解从任意一点开始到另一点的最短路径，但该算法极其耗时。 2. 广度优先搜索 Breadth First Search：单源最短路径算法，仅用于求解无权图。 3. 迪克斯特拉算法 Dijkstra Algorithm：单源最短路径算法，是广度优先搜索算法的加强版。Dijkstra 算法不能处理带有负权边的情况，更不能处理带有负权回路的图。 4. 贝尔曼福特算法 Bellman-Ford Algorithm：单源最短路径算法，可以用于处理又负权边的情况。对其进行队列优化后就变成了我们熟知的 SPFA 算法。 5. 弗洛伊德算法 Floyd Algorithm：多源最短路径算法，基于动态规划思想，能够一次性求出图中任意两点之间的最短路径，但该算法的时间复杂度非常高，达到惊人的 O(N3)O(N^3)O(N3)。弗洛伊德算法能处理带有负权边的情况，但不能处理带有负权回路的图。 为了方便阅读，本文提供的所有代码均会使用 vector 实现的邻接表来存图。 场景引入 在下图中，有 777 条不同的边，每一条路径上方都标记了一个数值 TiT_iTi ，代表通过该条路径所需要的时间。Macw 想知道从 111 号顶点到 555 号顶点所需要花费的最短时间。 不难看出，Macw 所需要花费的最短时间是 141414 分钟，一条可行的方案是从 111 号顶点出发，途径 222，333 号顶点到达顶点 555。虽然人脑可以很快的看出来，但是在庞大的数据量下，人的脑力就显得极其渺小。那对于计算机来说，我们如何能找到一条从 111 号节点到 555 号节点的路径呢？不妨让计算机暴力枚举出所有的可行路径和每条路径分别的耗时，取最小的那一条路径就可以了。深度优先搜索算法是一个选择。 深度优先搜索 DEPTH FIRST SEARCH 如上图所示，从 111 号节点到 555 号节点共有四条路径，每条路径和其分别耗时如下： 1. 1→2→51\to 2\to 51→2→5，耗时 2+16=182 + 16 = 182+16=18 分钟。 2. 1→2→3→51\to 2\to 3\to 51→2→3→5，耗时 2+7+5=142 + 7 + 5 = 142+7+5=14 分钟。 3. 1→4→51\to 4\to 51→4→5，耗时 6+12=186 + 12 = 186+12=18 分钟。 4. 1→4→3→51 \to 4\to 3\to 51→4→3→5，耗时 6+6+5=176 + 6 + 5 = 176+6+5=17 分钟。 其中第二个方案是最优解，耗时 141414 分钟。因此，一个可行的算法方案是使用深度优先搜索暴力枚举出所有可行的路径并记录最小值即可，其代码实现如下： 深度优先嗖嗖算法虽然很有效，但是该算法的运行效率太低下了，只适用于数据量较小的情况。假设图是一个二叉树树形结构，那么在最坏的情况下，这个算法的时间复杂度将会达到 O(2N)O(2^N)O(2N)。当每个顶点的度越多，深度优先搜索算法的时间复杂度就高。因此，在一般情况下，我们不会使用深度优先搜索。 设想在二维 N×MN \times MN×M 地图问题的情况下，我们怎么找到从入口到出口的最佳路径？一般情况下，我们会使用广度优先搜索的算法。广度优先搜索算法的复杂度远远低于深度优先搜索。 广度优先搜索算法 BREADTH FIRST SEARCH 在一个无权图中（或图中所有边的权值均为 111）的情况下，我们会使用广度优先搜索算法来实现。广度优先搜索算法的代码也很简洁： 我们已经知道，在一般的地图问题中广度优先搜索的效率非常高。那我们是否可以加以改进广度优先算法，让它适配带权图呢？答案是可以的，经过改编后的算法就是大名鼎鼎的 Dijkstra 算法。 迪克斯特拉算法 DIJKSTRA ALGORITHM Dijkstra 算法是一种用于寻找图中从单一源节点到其他所有节点的最短路径的算法（即单源最短路径算法）。它适用于所有边权重为非负值的图。这个算法最早是被荷兰计算机科学家 艾兹赫尔·戴克斯特拉 (Edsger W. Dijkstra) 发明并提出的，因此用他的名字来命名该最短路算法。 Dijkstra 算法的基本思想是逐步扩展最短路径，直到覆盖所有节点。依旧以「场景引入」章节的图来举例子，虽然我们没有办法一下子立刻求解出从 111 号节点到 555 号节点的最短路径，但是如果我们能求出从 111 号节点到 555 号节点所有的前驱节点的最短路径，那么我们就可以立刻计算出从起点到 555 号节点最短路。 如上图所示，555 号节点有三个前驱节点，分别是节点 V={2,3,4}V = \{2, 3, 4\}V={2,3,4}，走到这三个节点的最短距离分别为两分钟、九分钟和六分钟。通过遍历这些前驱节点，我们就可以求出从起点到终点的最短路。显然，对于图中所有的节点，我们都需要按照一定的顺序依次对它们进行相同的操作。这样子，我们就可以求解出从起点开始到图中任意一个点的最短距离了。 Dijkstra 算法具体的实现流程如下： 1. 初始化： * 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 000，其他所有节点的距离为 +∞+\infty+∞ 。 * 将所有节点标记为未访问。 * 使用一个优先队列来存储节点及到某一个节点当前所计算出的最短距离。 2. 选择节点： * 从未访问的节点中选择当前距离最小的节点作为当前节点。 * PS：如没有特殊情况，一开始这个节点应该是求解最短路问题的起点（起点与自己的距离应该是 000，正如初始化步骤中所提及的）。 3. 更新节点： * 对于当前节点的每个邻居节点，计算从当前节点到该邻居节点的距离。 * 如果这个距离小于已知的到该邻居节点的距离，则更新该邻居节点的距离。 * 距离更新: 对于每个邻居节点，计算从起点到该邻居节点的距离，如果该距离小于已知的最短距离，则更新最短距离。 4. 标记已访问： * 将当前节点标记为已访问，表示已经处理完了该节点。 * PS：当节点被标记完已访问后，从起点到该节点的最短距离就已经被正式确定下来了，在后续的计算过程中该节点的距离将不会再被更新。标记节点已访问可以在「选择节点」步骤完成后时就进行。换句话说，第三步和第四步的顺序并不重要。 5. 重复循环： * 重复上述提到的第 2-4 步，直到所有的点都被标记为已访问。 以下是使用 Dijkstra 算法对例题的模拟过程： 首先初始化距离数组，将源点的距离设置为 000，将除源点以外的所有点的距离设置为 +∞+\infty+∞。正无穷大表示到达该点的最短距离还未知。 从未访问的节点中选择当前距离最小的节点作为当前节点。在一开始，距离最小的节点就是源点本身。如下图，浅绿色表示当前选中的节点，黄色表示该节点的邻居节点。接下来就开始更新两个邻居节点距源点的最近距离。从 111 号点到 222 号点的最短距离为 222，而 222 号节点当前所记录的最短距离是 +∞+\infty+∞，比较发现 2<+∞2 < +\infty2<+∞，因此将 222 号点的距离从原本的正无穷更新为 222。节点 444 也是如此，从起点到该节点的最短路径将由原本的正无穷更新为 666。 此时，111 号节点已经处理完成了，我们将该节点标记为已访问（图中用深绿色表示）。接下来，我们从未访问的节点当中选择一个距离最小的节点作为当前节点。如下图，未访问的节点有 V={2,3,4,5}V = \{2, 3, 4, 5\}V={2,3,4,5}，其当前的距离分别为 Dis={2,+∞,6,+∞}Dis = \{2, +\infty, 6, +\infty\}Dis={2,+∞,6,+∞}，因此我们选择 222 号节点作为新的当前节点，因为该节点是所有未访问节点当中距离源点距离最小的那个节点。 从 222 号节点开始，更新该节点的所有邻居节点。对于 555 号节点，原本的距离是 +∞+\infty+∞，但从源点出发，经过 222 号节点的距离为 2+16=182 + 16 = 182+16=18，显然这个距离比原本的正无穷大更优，因此更新该节点的最短距离为 181818。对于 333 号节点也是如此，从源点出发经过 222 号节点的最短距离是 2+7=92 + 7 = 92+7=9，因此将 333 号节点的距离更新为 999。 将 222 号节点标记为已访问。接下来再从未访问的节点中选择一个距离最近的节点，现在未访问的节点有 V={3,4,5}V = \{3, 4, 5\}V={3,4,5}，其中 444 号节点的距离最短，因此选择 444 号节点作为当前节点。从 444 号节点出发可以到达的节点只有 333 号节点，如果从源点出发经过 444 号节点再到 333 号节点的距离为 6+6=126 + 6 = 126+6=12，这显然比当前 333 号的距离更大，因此这不是一个更优的解，本轮将不再更新 333 号节点的最短距离。 将 444 号节点标记为已访问。现在再从未访问的节点中选择一个距离最小的节点作为当前节点，因此我们将选择 333 号节点作为当前节点。我们发现从源点出发经过 333 号节点到 555 号节点的距离为 9+5=149 + 5 = 149+5=14，这比 555 号节点当前记录的 181818 更优，因此更新 555 号节点的最短距离。 将 333 号节点标记为已访问。 选择 555 号节点作为当前节点。由于 555 号节点没有任何的后继节点，因此循环结束。将 555 号节点标记为已访问。 至此，所有的节点都标记为已访问，Dijkstra 算法结束。此时距离数组记录的值就是从源点出发到各个点的最短距离。 在下方代码中，为了快速的找到当前距离最小的节点，我们将会使用 C++ 自带的优先队列 (Priority Queue) 数据结构来实现。 完整的 Dijkstra 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1）： 由于该算法是基于优先队列实现的，优先队列求出最小值的复杂度为 O(log2(V))O(log_2(V))O(log2 (V))（使用了二叉堆优化），因此 Dijkstra 的时间复杂度约为 O((V+E)×log2V)O((V + E) \times log_2{V})O((V+E)×log2 V)，其中 VVV 代表图中顶点的数量，EEE 代表图中边的数量。相比之下，Dijkstra 算法的运行效率非常优越。该算法也是在求解最短路问题中应用最广泛的算法之一。 贝尔曼福特算法 BELLMAN-FORD ALGORITHM Bellman-Ford 算法也是一种用于求解单源最短路径问题的算法，特别适用于含有负权边的图。与 Dijkstra 算法不同，Bellman-Ford 算法能够检测到负权重环路的存在。 Bellman-Ford 的算法思想是通过 松弛操作 (Relaxation) 逐步找到从源点到所有其他顶点的最短路径。对一条边进行松弛操作指的是检查一条边/图上的路径是否能提供更短的路径。如果可以，那么就更新答案。 该算法会重复对图中的所有边进行松弛操作，总共执行 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次，其中 ∣V∣\lvert V\rvert∣V∣ 是图中顶点的数量。 Bellman-Ford 算法具体的实现流程如下： 1. 初始化： * 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 000，其他所有节点的距离为 +∞+\infty+∞ 。 2. 松弛操作： * 对于每一条边 (u,v)(u, v)(u,v)，和这条边的权重 w(u,v)w(u, v)w(u,v)，如果可以使得 disu+w(u,v)<disvdis_u + w(u, v) < dis_vdisu +w(u,v)<disv ，则将 disvdis_vdisv 更新为 disu+w(u,v)dis_u + w(u, v)disu +w(u,v)。其中，disidis_idisi 表示编号为 iii 节点的距离。 * 重复上述步骤 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次。 3. 检测是否存在负环： * 再次对所有边执行松弛操作。如果发现某条边 (u,v)(u, v)(u,v) 仍能使 disu+w(u,v)<disvdis_u + w(u, v) < dis_vdisu +w(u,v)<disv 成立，则说明图中存在负权重环路。 * 换句话说，如果一个图不存在负环，则这张图的边在经历最多 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次松弛操作后将不能再进行松弛了。 以下是使用 Bellman-Ford 算法对例题的模拟过程： 首先初始化距离数组，将源点的距离设置为 000，将除源点以外的所有点的距离设置为 +∞+\infty+∞。正无穷大表示到达该点的最短距离还未知。 选择一条边，对该边尝试进行一次松弛操作。如下图（红色的边表示当前选中的边），通过这一条边可以将从源点到 222 号点的距离从正无穷大缩短至 222，因此更新新的距离。 以次类推，依次遍历并尝试松弛所有的边。当每一条边经历 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次松弛操作后，算法结束。此时距离数组记录的值就是从源点出发到各个点的最短距离。 完整的 Bellman-Ford 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1，由于标准版的 Bellman-Ford 算法运行效率低下，因此不保证可以通过所有的测试点）： 使用 Bellman-Ford 算法判断负环的方法如下（对应例题：ACGO - A551.单源最短路径2）： 因为 Bellman-Ford 算法要对每条边进行 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次松弛操作，并且还需要判断一次是否存在负环，因此该算法的时间复杂度为 O(V×E)O(V \times E)O(V×E)，其中 VVV 是顶点数，EEE 是边数。Bellman-Ford 的时间复杂度相对来说比较高，因此在没有负环的时候仍然推荐使用 Dijkstra 最短路算法作为首选方案。 SPFA 算法 SHORTEST PATH FASTER ALGORITHM SPFA (Shortest Path Faster Algorithm) 算法是 Bellman-Ford 算法的改进版本，专门用于加速单源最短路径的计算。该算法通过队列机制减少了不必要的松弛操作，从而提高了代码的运行效率。SPFA算法在实践中表现出优异的性能，特别是在稀疏图中。 SPFA 算法利用一个队列来存储需要松弛的顶点，并且每个顶点在队列中最多出现一次。通过这种机制，SPFA 算法避免了对所有边进行多余的松弛操作，从而提高了效率。 但 SPFA 算法也有缺陷，在一些特殊的情况下，可能会出现卡死的情况（有一句古话：关于 SPFA，它死了）。在最坏的情况下，SPFA 的复杂度高达 O(V×E)O(V\times E)O(V×E)（就是普通 Bellman-Ford）算法的运行效率。但该算法在大多数情况下表现优异，通常情况该算法的平均时间复杂度在 O(V+E)O(V + E)O(V+E) 附近，其中 VVV 是图中顶点的数量，EEE 是图中边的数量。 SPFA 算法具体的实现流程如下： 1. 初始化： * 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 000，其他所有节点的距离为 +∞+\infty+∞ 。 * 初始化一个队列（不需要是优先队列，普通队列即可）。将源点加入到队列之中。 * 初始化一个数组用来记录某个顶点是否在队列之中。在程序开始时，源点应该被标记为已经入队。 2. 松弛操作： * 对于每一条边 (u,v)(u, v)(u,v)，和这条边的权重 w(u,v)w(u, v)w(u,v)，如果可以使得 disu+w(u,v)<disvdis_u + w(u, v) < dis_vdisu +w(u,v)<disv ，则将 disvdis_vdisv 更新为 disu+w(u,v)dis_u + w(u, v)disu +w(u,v)。其中，disidis_idisi 表示编号为 iii 节点的距离。 * 如果成功进行了松弛操作，且顶点 vvv 不在队列之中，那么将顶点 vvv 加入到队列之中。 3. 重复执行： * 重复第二部的操作，直到队列为空。 * PS：如果某个点加入了队列 ∣V∣\lvert V\rvert∣V∣ 次，则说明该图存在负环，应该立结束程序。 以下是使用 SPFA 算法对例题的模拟过程： 首先初始化距离数组，将源点的距离设置为 000，将除源点以外的所有点的距离设置为 +∞+\infty+∞。正无穷大表示到达该点的最短距离还未知。同时，将源点加入到队列之中，并将源点标记为已加入队列。 选择队首元素（在当前情况就是 111 号节点），松弛与 111 号节点相邻的两条边。从 111 号节点出发，到 222 号节点和 444 号节点的距离都比正无穷大要小，因此更新这两个节点的距离。与此同时，由于 222 号节点和 444 号节都不在队列中，因此将这两个节点加入到队列。 弹出位于队首的 111 号元素，选择位于队首的 222 号元素，松弛与 222 号节点相邻的两条边。从 222 号节点出发，到 333 号节点和 555 号节点的距离都比正无穷大要小，因此更新这两个节点的距离。与此同时，由于 333 号节点和 555 号节都不在队列中，因此将这两个节点加入到队列。 弹出位于队首的 222 号元素，选择位于队首的 444 号元素，松弛与 444 号节点相邻的两条边。从 444 号节点出发，到 333 号节点和 555 号节点的距离都比原本要远，因此不更新任何节点，也不将任何节点加入到队列当中。 弹出位于队首的 444 号元素，选择位于队首的 333 号元素，松弛与 333 号节点相邻的两条边。从 333 号节点出发，到 555 号节点的距离为 9+5=149 + 5 = 149+5=14，比原本的 181818 要更优，因此更新 555 号节点。但由于 555 号节点已经被加入到了队列之中，因此不再重复加入。 弹出位于队首的 333 号元素，选择位于队首的 555 号元素，由于该节点不存在任何的后继节点，因此不做任何操作，直接将 555 号节点弹出队列。至此，队列为空，SPFA 算法结束。 完整的 SPFA 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1，由于标准版的 SPFA 算法最坏的情况会被卡死，因此不保证可以通过所有的测试点）： 使用该算法判断负环，只需要判断是否存在一个节点被加入了超过 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次即可。完整的 SPFA 判断是否存在负环的代码如下（对应例题：洛谷 - P3385 【模板】负环）： 弗洛伊德算法 FLOYD ALGORITHM Floyd 算法运用了动态规划的思想，该算法用于求解所有顶点对之间的最短路径问题。Floyd 算法适用于带权有向图，可以处理负权重边，但不能处理图中含有负权重环的情况。 Floyd l算法通过三重循环迭代地更新最短路径。设定一个二维矩阵 DisDisDis，其中 Disi,jDis_{i, j}Disi,j 表示从顶点 iii 到顶点 jjj 的最短路径权重。初始时，将直接相连的顶点的距离设置为边的权重，没有直接连接的顶点距离设为无穷大，顶点到自身的距离设为 000。 该算法的核心思想是，检查每一对顶点 (i,j)(i, j)(i,j) 是否可以通过另一个顶点 kkk（作为中转节点） 使得从 iii 节点到 jjj 节点的路径更优。如果通过 kkk 可以使路径更短，则更新 Disi,jDis_{i, j}Disi,j 。 因此可以得到状态转移方程：Disi,j=min⁡(Disi,k+Disk,j,Disi,j)Dis_{i, j} = \min(Dis_{i, k} + Dis_{k, j}, Dis_{i, j})Disi,j =min(Disi,k +Disk,j ,Disi,j )。 综上所述，Floyd 的代码如下（对应例题：洛谷 - B3647 【模板】Floyd）： Floyd 算法的时间复杂度在 O(N3)O(N^3)O(N3)，其中 NNN 表示图中顶点的数量。因此该算法的执行效率是极其低的，在没有特殊情况下，尽量避免使用该算法。但如果遇到多源最短路径的题目，Floyd 算法还是首选方案。 DIJKSTRA 算法和 SPFA 算法的主要区别 1. 处理负权边： * SPFA：可以处理负权边，并且在某些情况下表现出色。SPFA还可以检测负权环。 * Dijkstra：无法处理负权边，因为 Dijkstra 算法假设已经找到的最短路径，且不会被后续路径更新。 2. 队列机制： * SPFA：使用一个队列来存储需要处理的顶点。顶点可能多次进入队列，但每次只有在更短路径被发现时才重新入队。 * Dijkstra：使用优先队列（通常是最小堆）来存储顶点，以确保每次处理的顶点是当前最短路径确定的顶点。 3. 时间复杂度： * SPFA：在实际应用中通常表现良好，平均时间复杂度为 O(V+E)O(V + E)O(V+E)，但最坏情况下为 O(V×E)O(V\times E)O(V×E)。 * Dijkstra：使用最小堆实现时，时间复杂度为 O((V+E)×log2V)O((V + E)\times log_2V)O((V+E)×log2 V)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本期讲解了常见的几种求解最短路问题的算法，共计 8409 字。谢谢阅读。