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
相关推荐
在okr拆解的小太阳...：实习待过，我待的部门氛围很好，基本不加班，双休有保证。
投递正浩创新EcoFlow等公司10个岗位 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 什么是优秀的实习经历 #
8189次浏览 206人参与
# 实习简历求拷打 #
11470次浏览 146人参与
# 被上班搭子“传染”了哪些习惯 #
5421次浏览 97人参与
# 秋招被挂春招仍然能投的公司 #
6584次浏览 94人参与
# 工作后，你落下了哪些病根 #
13148次浏览 184人参与
# mt对你说过最有启发的一句话 #
35125次浏览 419人参与
# 摸鱼被leader发现了怎么办 #
100787次浏览 641人参与
# 考研失败就一定是坏事吗？ #
200819次浏览 1369人参与
# 秋招特别不鸣谢 #
15503次浏览 176人参与
# 选实习，你更看重哪方面？ #
13811次浏览 215人参与
# 作业帮求职进展汇总 #
82776次浏览 545人参与
# 今年秋招你收到了多少封邮件？ #
17883次浏览 219人参与
# 机械/制造每日一题 #
80233次浏览 1411人参与
# 第一次面试 #
1036405次浏览 13682人参与
# 携程求职进展汇总 #
839912次浏览 5530人参与
# 毕业论文进行时 #
20855次浏览 131人参与
# 工作中遇到的歹人 #
27908次浏览 313人参与
# 京东美团大战，你怎么看？ #
158016次浏览 859人参与
# 你今年的保底offer是哪家 #
155068次浏览 671人参与
# 找工作有哪些冷知识 #
205810次浏览 2607人参与