coldfresh
2021-09-17 22:47 同济大学 C++
关注
总的来说只有第三题难度稍大，这里讲一下思路。考建图（也就是拆点）和最短路（优先队列）这里考虑建立n*2个点，x和x+n建边，边权为1，但是如果转移到x的时候不是传送过来的，那么就不需要加这个这个开销，这里是需要判断的，所以需要保存状态，dis[0][x]表示转移到x这个点的前一个点不是传送过来的，反之dis[1][x]表示是传送到这个点的。其实如果大家有体会，图论难起来就感觉和dp有相似的感觉，其实就本质来说也就是所谓的松弛操作，一种适合在图上转移状态的方法。ac代码见评论。一次ac，但是调试了有点时间。
查看原帖
点赞 1
相关推荐
查看45道真题和解析 点赞 评论 收藏
分享
zachsun：华科硕士给13级？有点逆天了吧 点赞 评论 收藏
分享
CUG芝士圈：虽然是网上的项目，但最好还是包装一下，然后现在大部分公司都在忙校招，十月底、十一月初会好找一些。最后，boss才沟通100家，别焦虑，我去年暑假找第一段实习的时候沟通了500➕才有面试
，校友加油
点赞 评论 收藏
分享
牛客热帖
正在热议
# 25届秋招总结 #
351218次浏览 3421人参与
# 我的实习求职记录 #
6084297次浏览 83670人参与
# 北方华创开奖 #
49703次浏览 448人参与
# 地方国企笔面经互助 #
5180次浏览 13人参与
# 职场吐槽大会 #
90599次浏览 751人参与
# 选完offer后，你后悔学本专业吗 #
22961次浏览 165人参与
# 百度开奖 #
212824次浏览 1346人参与
# ai智能作图 #
2944次浏览 65人参与
# 运营商笔面经互助 #
92586次浏览 1333人参与
# 实习中的菜狗时刻 #
278744次浏览 2739人参与
# 腾讯求职进展汇总 #
199289次浏览 1660人参与
# 阿里求职进展汇总 #
70832次浏览 761人参与
# 如果有时光机，你最想去到哪个年纪？ #
24597次浏览 501人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
37387次浏览 343人参与
# 风评不好的公司，你会去吗？ #
20692次浏览 94人参与
# 上班苦还是上学苦呢？ #
90328次浏览 780人参与
# 大疆求职进展汇总 #
413410次浏览 2934人参与
# 国企还是互联网，你怎么选？ #
90121次浏览 699人参与
# 远程面试的尴尬瞬间 #
20433次浏览 294人参与
# 软件开发2024笔面经 #
2325536次浏览 48219人参与
# 如何一边实习一边秋招 #
999806次浏览 12697人参与
# 如果中了500万，你会离职吗？ #
13484次浏览 144人参与