如果你 WA on #15 (血的教训)
查看原帖
如果你 WA on #15 (血的教训)
90027
fanypcd楼主2022/5/19 23:53

正常写 dijkstra 的时候应该是用小根堆取出队列中 dis 最小的点。

如果你这里维护队列时没有将点进队时的树根存下来(只存点的编号,比较函数内用当前动态维护的树根比较),就会寄在 #15,大概长这样:

原因是这个点进队后可能 dis 值会被更新(意味着对应的线段树树根会变),然后你不存进队时的根(即 dis 值),队列维护就可能会出问题。

别问我怎么知道的。。

2022/5/19 23:53
加载中...