首页 > 代码库 > 求经过路径最少的最短路

求经过路径最少的最短路

题目保证最短路不止一条,求经过路径最少的最短路.
分析:假设数据小的话能够用floyed+Dp求出。在保证最短路的情况下更新路径少的情况就可以,dis表示最短路,大盘dp[i,j]表示从i到j的最短路所需最少路径条数;但一旦数据大于300,非常有超时危急,以下是一个小技巧:将边权乘以10^8后+1(注意乘以几要视数据大小而定),再用高效的spfa或堆优化的dijkstra来跑。


为什么呢?举个样例:假定边数不超过100000(10的5次方),而边权*10^8后能够说远大于它,那么在更新最短路时+1会算入距离,就能够将其视为路径数,随最短路更新而自己主动更新。


最后跑完后取出走后几位数就可以。即为经过路径最少的最短路的经过路径数。

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

求经过路径最少的最短路