某种基于SPFA的复杂度并不正确但跑的飞快的求图上单个点的多个不同走法要求的最短路且各种走法相互关联的算法既CF553E 【Kyoya and Train】题解

不要问我为什么标题这么奇怪,我也不知道我在写什么(
做CF题的时候碰到的
当然正如标题所说,这篇题解里的复杂度讲的并不正确,因为各种走法要求的最短路相互关联,因此对于一种走法的最短路的长度并不能保证,当然跑得飞快就是了(
正解是分治FFT,不过最开始没注意到有环,莽出来莽错了,改spfa比较方便,就懒得再写分治FFT了(

评论

此博客中的热门博文