建两张图,i->j 的有向边作为正图,j->i的逆边作为反图;这样正图一遍 dijistra 计算 1到其它点的最短路;反图一遍 dijistra 计算N到其它点的最短路; 每次的查询Q只用更新 d(1, i) + d(i, j) + d(j, N) 是否比 d(1, N) 短就行了
点赞 3

相关推荐

05-23 20:31
已编辑
武汉大学 Java
内向的柠檬精在研究求职打法:注意把武大标粗标大 本地你俩不是乱杀
点赞 评论 收藏
分享
鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务