我们知道朴素版Dijkstra可以在O(n^2)的复杂度内处理出单个点到全图的单源最短路.但这一题要求从第i个点回到原点。所以在我们求出从原点出发到其余点的最短距离后,还有遍历从各个点出发到原点的最短距离,也就是O(n^3) 注意到i->1的最短路等价于1沿着反向边到i的最短路,最后分别以1为起点做两次朴素dj,但是第二次是反向建图
点赞

相关推荐

04-24 18:13
南京大学 Java
不吃酸菜血肠:看力竭了
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务