<div class="blogpost-body" id="cnblogs_post_body">
<p>优化一：每次更新节点时，记录当前走的这条路径的节点数，当节点数大于n时，有负环，退出。注意，这里与常规的节点被更新n次以上退出不一样，效率比常规高。</p>
<p>优化二：双端队列SLF优化。当当前节点到起点距离小于队首的时候，将此点插入队首，否则，正常插入队尾。可能咋一看感觉这种优化可能被用到的机会很少，但很可能正好解决掉了专门卡spfa的数据以及网格图。</p>
<p>优化三：与优化二类似，但改为小于队列元素平均数时加入队首，还没试过。</p>
<p>附上一道用spfa但以上优化效果很明显的一道题</p>
<p>http://codeforces.com/gym/101498/problem/L</p>
<p>不加优化2500ms左右（TLE边缘），加入优化一和优化二后311ms。</p>
<div class="cnblogs_code">
<img alt="" class="code_img_closed" id="code_img_closed_a5ce3cab-d0dd-442f-af4b-ac56c41d3b9c" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-8f900a89c6347c561fdf2122f13be562.gif">
<img alt="" class="code_img_opened" id="code_img_opened_a5ce3cab-d0dd-442f-af4b-ac56c41d3b9c" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-961ddebeb323a10fe0623af514929fc1.gif">
<div class="cnblogs_code_hide" id="cnblogs_code_open_a5ce3cab-d0dd-442f-af4b-ac56c41d3b9c">
<pre class="blockcode"><span style="color:#008080;"> 1</span> #include <iostream>
<span style="color:#008080;"> 2</span> #include <fstream>
<span style="color:#008080;"> 3</span> #include <sstream>
<span style="color:#008080;"> 4</span> #include <cstdlib>
<span style="color:#008080;"> 5</span> #include <cstdio>
<span style="color:#008080;"> 6</span> #include <cmath>
<span style="color:#008080;"> 7</span> #include <<span style="color:#0000ff;">string</span>>
<span style="color:#008080;"> 8</span> #include <cstring>
<span style="color:#008080;"> 9</span> #include <algorithm>
<span style="color:#008080;"> 10</span> #include <queue>
<span style="color:#008080;"> 11</span> #include <stack>
<span style="color:#008080;"> 12</span> #include <vector>
<span style="color:#008080;"> 13</span> #include <<span style="color:#0000ff;">set</span>>
<span style="color:#008080;"> 14</span> #include <map>
<span style="color:#008080;"> 15</span> #include <list>
<span style="color:#008080;"> 16</span> #include <iomanip>
<span style="color:#008080;"> 17</span> #include <cctype>
<span style="color:#008080;"> 18</span> #include <cassert>
<span style="color:#008080;"> 19</span> #include <bitset>
<span style="color:#008080;"> 20</span> #include <ctime>
<span style="color:#008080;"> 21</span>
<span style="color:#008080;"> 22</span> <span style="color:#0000ff;">using</span> <span style="color:#0000ff;">namespace</span><span style="color:#000000;"> std;
</span><span style="color:#008080;"> 23</span>
<span style="color:#008080;"> 24</span> <span style="color:#0000ff;">#define</span> pau system("pause")
<span style="color:#008080;"> 25</span> <span style="color:#0000ff;">#define</span> ll long long
<span style="color:#008080;"> 26</span> <span style="color:#0000ff;">#define</span> pii pair<int, int>
<span style="color:#008080;"> 27</span> <span style="color:#0000ff;">#define</span> pb push_back
<span style="color:#008080;"> 28</span> <span style="color:#0000ff;">#define</span> mp make_pair
<span style="color:#008080;"> 29</span> <span style="color:#0000ff;">#define</span> clr(a, x) memset(a, x, sizeof(a))
<span style="color:#008080;"> 30</span>
<span style="color:#008080;"> 31</span> <span style="color:#0000ff;">const</span> <span style="color:#0000ff;">double</span> pi = acos(-<span style="color:#800080;">1.0</span><span style="color:#000000;">);
</span><span style="color:#008080;"> 32</span> <span style="color:#0000ff;">const</span> <span style="color:#0000ff;">int</span> INF = <span style="color:#800080;">0x3f3f3f3f</span><span style="color:#000000;">;
</span><span style="color:#008080;"> 33</span> <span style="color:#0000ff;">const</span> <span style="color:#0000ff;">int</span> MOD = 1e9 + <span style="color:#800080;">7</span><span style="color:#000000;">;
</span><span style="color:#008080;"> 34</span> <span style="color:#0000ff;">const</span> <span style="color:#0000ff;">double</span> EPS = 1e-<span style="color:#800080;">9</span><span style="color:#000000;">;
</span><span style="color:#008080;"> 35</span>
<span style="color:#008080;"> 36</span> <span style="color:#008000;">/*</span>
<span style="color:#008080;"> 37</span> <span style="color:#008000;">#include <ext/pb_ds/assoc_container.hpp>
</span><span style="color:#008080;"> 38</span> <span style="color:#008000;">#include <ext/pb_ds/tree_policy.hpp>
</span><span style="color:#008080;"> 39</span>
<span style="color:#008080;"> 40</span> <span style="color:#008000;">using namespace __gnu_pbds;
</span><span style="color:#008080;"> 41</span> <span style="color:#008000;">tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T;
</span><span style="color:#008080;"> 42</span> <span style="color:#008000;">*/</span>
<span style="color:#008080;"> 43</span>
<span style="color:#008080;"> 44</span> <span style="co |
|
转播
