关注
总的来说只有第三题难度稍大,这里讲一下思路。考建图(也就是拆点)和最短路(优先队列)这里考虑建立n*2个点,x和x+n建边,边权为1,但是如果转移到x的时候不是传送过来的,那么就不需要加这个这个开销,这里是需要判断的,所以需要保存状态,dis[0][x]表示转移到x这个点的前一个点不是传送过来的,反之dis[1][x]表示是传送到这个点的。其实如果大家有体会,图论难起来就感觉和dp有相似的感觉,其实就本质来说也就是所谓的松弛操作,一种适合在图上转移状态的方法。ac代码见评论。一次ac,但是调试了有点时间。
查看原帖
点赞 1
相关推荐
05-10 14:31
华南师范大学 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 我的实习收获 #
30434次浏览 500人参与
# 如果有时光机,你最想去到哪个年纪? #
47113次浏览 800人参与
# 实习吐槽大会 #
32302次浏览 155人参与
# 非技术岗简历怎么写 #
209758次浏览 2861人参与
# 晒一晒你的工位 #
85775次浏览 304人参与
# 26届秋招投递记录 #
3795次浏览 106人参与
# 2025牛客秋招季 #
4200次浏览 130人参与
# 双非能在秋招上岸吗? #
215174次浏览 1142人参与
# 被AI治愈的瞬间 #
52314次浏览 597人参与
# 怎么防止在试用期被辞退 #
122327次浏览 911人参与
# 我的租房踩坑经历 #
27805次浏览 284人参与
# 穿越回高考你还会选现在的专业吗 #
21729次浏览 266人参与
# 我和mentor的爱恨情仇 #
43635次浏览 278人参与
# 打工人的工作餐日常 #
40437次浏览 343人参与
# 软开人,说说你的烦心事 #
48093次浏览 359人参与
# 毕业旅行去哪玩儿 #
1243次浏览 33人参与
# 硬件/芯片公司工作体验 #
75202次浏览 664人参与
# 商战,最累的是我们 #
13058次浏览 52人参与
# 打工人锐评公司红黑榜 #
145976次浏览 920人参与
# 25届秋招公司红黑榜 #
262160次浏览 1094人参与