最便宜的车票题解
题意是求最短路，可以选择一个点使得与这个点相连的所有边边权变为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++
关注
全部评论
相关推荐
03-02 08:18
集美大学 Java 
没有赛事奖项么？另外，项目经历字有点多哈，建议突出一下重点：用的什么技术，解决什么问题，达到什么效果。 点赞 评论 收藏
分享
04-03 23:26
门头沟学院 前端工程师 点赞 评论 收藏
分享