总的来说只有第三题难度稍大,这里讲一下思路。考建图(也就是拆点)和最短路(优先队列)这里考虑建立n*2个点,x和x+n建边,边权为1,但是如果转移到x的时候不是传送过来的,那么就不需要加这个这个开销,这里是需要判断的,所以需要保存状态,dis[0][x]表示转移到x这个点的前一个点不是传送过来的,反之dis[1][x]表示是传送到这个点的。其实如果大家有体会,图论难起来就感觉和dp有相似的感觉,其实就本质来说也就是所谓的松弛操作,一种适合在图上转移状态的方法。ac代码见评论。一次ac,但是调试了有点时间。
点赞 1

相关推荐

墨西哥大灰狼:如果你的校友卤馆还在的话,他肯定会给你建议的,可是卤馆注销了@ 程序员卤馆
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务