最便宜的车票题解
题意是求最短路，可以选择一个点使得与这个点相连的所有边边权变为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)的。
2021-04-01 12:52 已编辑 西北农林科技大学
关注
全部评论
相关推荐
携程开奖24人在聊 点赞 评论 收藏
转发
点赞 评论 收藏
转发