~~O2优化~~
by Absurdity @ 2019-11-11 16:39:06
在松弛的时候存储
pre[to] = i 用终点来记录边
by twilight_moon @ 2019-11-11 16:41:21
@[Mysterious_wind](/user/122953)
~~O2过了~~
by kakao @ 2019-11-11 16:51:22
@[twilight_moon](/user/135866) 是专门开一个数组来存吗？
by kakao @ 2019-11-11 16:51:52
@[麒然](/user/105266) 不是吧，他的意思也许是不存边的起点，也就是不用head[]，用pre[]存终点。
by Absurdity @ 2019-11-11 16:57:14
@[Mysterious_wind](/user/122953) 还是不理解，用终点存边和记录最短路经过哪些边有什么关系吗？
by kakao @ 2019-11-11 17:06:55
@[麒然](/user/105266) 我也觉得用终点存没有什么优化，~~所以既然这一题SPFA常数不大，那就跑SPFA吧~~
by Absurdity @ 2019-11-11 17:11:44
@[麒然](/user/105266)
是的鸭
或者你可以正着跑一遍dijk
反着跑一遍
只要满足
dis[i] + tu[j].val + disf[tu[j].to] == yuan || dis[tu[j].to] + tu[j].val + disf[i] == 最短路长度
就可以证明他是最短路上的边
by twilight_moon @ 2019-11-11 17:46:38
@[麒然](/user/105266) 你可以跑2遍dij（正的和反的）然后判断一条边是否为最短路上的边，然后枚举这些边就好
by 取啥名好 @ 2019-11-11 17:46:52
@[取啥名好](/user/173397)
这个人是 憨憨
by twilight_moon @ 2019-11-11 17:47:40