同余类最短路

121 阅读 0 评论 80 点赞

我是靠谱客的博主心灵美玉米，最近开发中收集的这篇文章主要介绍同余类最短路，觉得挺不错的，现在分享给大家，希望可以做个参考。

考虑这样一个问题：

给定n个数，每次询问一个数q，可不可以由这n个数组成

设n个数中最小的数为a，对于0-a-1中的每个点i，向(i+xj)%a连一条权值为xj的边

跑一遍最短路，则距离数组的意义是在模a意义下，在所有可以组成的模a剩余i的数中，最小的数是多少

如果可以到达点i，则i+k*a都可以到达

因为是在模a的意义下，所以0到a-1的所有点就包括了所有可能组成的情况

例题：WC2016 论战捆竹竿

转载于:https://www.cnblogs.com/tuchen/p/10416485.html

以上就是心灵美玉米为你收集整理的同余类最短路的全部内容，希望文章能够帮你解决同余类最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。