最便宜的车票题解
题意是求最短路，可以选择一个点使得与这个点相连的所有边边权变为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 已编辑 西北农林科技大学 C++
关注
全部评论
相关推荐
投递Momenta等公司8个岗位 点赞 评论 收藏
分享
2025-12-06 17:39
中国石油大学（华东） 前端工程师 
rbjjj：太杂了吧，同学，项目似乎都没深度，都是api调度耶，分层架构思想没有体现出来了，前端没有前端优化前端工程化体现，后端微服务以及分层架构没体现以及数据安全也没体现，核心再改改，注重于计算机网络，工程化，底层原理吧
点赞 评论 收藏
分享