[Usaco2011 Jan]道路和航线

[Usaco2011 Jan]道路和航线
这题一眼看过去就是最短路呢,但是呢?好像有负环,啧啧Dij用不了啦!好像点有点多,Floyd用不了啦,就只剩下spfa啦,但是spfa在极限数据下还是会T掉呢?怎么办,这里引入Spfa其中一个优化SLF优化。全称Small Label First 策略
设要加入的节点是y,队首元素为x,若d[y] \lt d[x],则将y插入队首,否则插入队尾。
其实只要一个优化就可以了,但是为了测试多一下,我就再加了一个优化LLL优化,全称Large Label Last 策略
这样的话我们就可以用上双头队列deque了。
其他的就是普通跑一下spfa就好。
只有SLF优化的

加了双优化的,慢了好多,但是也学了学这种优化

发表评论

电子邮件地址不会被公开。 必填项已用*标注