最便宜的车票题解

题意是求最短路,可以选择一个点使得与这个点相连的所有边边权变为1。
假设我们选择的点是x,经过x的最短路是:
1—>......—>a—>x—>b—>......—>n
答案就是min{dis(1,a)+dis(b,n)+2},这里a和b要同时和一个点相连。
我们可以用最短路算法求出1和n到其他所有点的最短路,dij和spfa都是可以的。
然后再依次枚举点就好,复杂度总的来说,用dij的话,是O(nlogn+m)的。

全部评论

相关推荐

废铁汽车人:秋招真是牛鬼蛇神齐聚一堂
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务