首页 > 代码库 > 求经过路径最少的最短路
求经过路径最少的最短路
题目保证最短路不止一条,求经过路径最少的最短路.
分析:假设数据小的话能够用floyed+Dp求出。在保证最短路的情况下更新路径少的情况就可以,dis表示最短路,大盘dp[i,j]表示从i到j的最短路所需最少路径条数;但一旦数据大于300,非常有超时危急,以下是一个小技巧:将边权乘以10^8后+1(注意乘以几要视数据大小而定),再用高效的spfa或堆优化的dijkstra来跑。
为什么呢?举个样例:假定边数不超过100000(10的5次方),而边权*10^8后能够说远大于它,那么在更新最短路时+1会算入距离,就能够将其视为路径数,随最短路更新而自己主动更新。
最后跑完后取出走后几位数就可以。即为经过路径最少的最短路的经过路径数。
求经过路径最少的最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。