边权种数是常数时单源最短路能否做到线性?
  • 板块学术版
  • 楼主zimujun
  • 当前回复14
  • 已保存回复14
  • 发布时间2021/8/28 16:14
  • 上次更新2023/11/4 08:43:14
查看原帖
边权种数是常数时单源最短路能否做到线性?
118196
zimujun楼主2021/8/28 16:14

RT

刚才看到这个帖子,记得之前有大佬说过在边权只有两种的情形下,如果开两个队列,分别存用两种边权松弛的点,那么两个队列都是单调的,当时并没清楚如何证明,那么这个做法能否推广到边权的种类数是常数的情况?

2021/8/28 16:14
加载中...