程序蒟蒻

题解

/ 注册

全部文章 / 题解（共2篇）

【每日一题】9月11日题目精讲

SPFA+SLF优化，直接朴素的SPFA会卡掉。当然用SPFA+LLL+SLF应该也是可以的，但是我不是很会LLL，但是一个SLF优化就可以过了。题目当中说：双向边是非负的而单向边没有环，所以，我们可以先把有双向边链接的若干个点缩成一个点，然后点之间连上单向边之后这张图是一个有向无环图，所以跑广搜就...

spfa最短路

2020-09-14

0 636

【每日一题】8月6日题目精讲—追债之旅

思路：给最短路的dist数组加一维，表示现在是第几天（已经进过了几条边）把最短路松弛操作改为：if (dist[x][k+1] > dist[y][k] + w[x][y]) dist[x][k+1] = dist[y][k] + w[x][y];即可。模板是spfa #...

spfa最短路

2020-08-20

0 550