优化一：每次更新节点时，记录当前走的这条路径的节点数，当节点数大于n时，有负环，退出。注意，这里与常规的节点被更新n次以上退出不一样，效率比常规高。
优化二：双端队列SLF优化。当当前节点到起点距离小于队首的时候，将此点插入队首，否则，正常插入队尾。可能咋一看感觉这种优化可能被用到的机会很少，但很可能正好解决掉了专门卡spfa的数据以及网格图。
优化三：与优化二类似，但改为小于队列元素平均数时加入队首，还没试过。
附上一道用spfa但以上优化效果很明显的一道题
http://codeforces.com/gym/101498/problem/L
不加优化2500ms左右（TLE边缘），加入优化一和优化二后311ms。
1 #include <iostream> 2 #include <fstream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <cmath> 7 #include <string> 8 #include <cstring> 9 #include <algorithm> 10 #include <queue> 11 #include <stack> 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <list> 16 #include <iomanip> 17 #include <cctype> 18 #include <cassert> 19 #include <bitset> 20 #include <ctime> 21 22 using namespace std; 23 24 #define pau system("pause") 25 #define ll long long 26 #define pii pair<int, int> 27 #define pb push_back 28 #define mp make_pair 29 #define clr(a, x) memset(a, x, sizeof(a)) 30 31 const double pi = acos(-1.0); 32 const int INF = 0x3f3f3f3f; 33 const int MOD = 1e9 + 7; 34 const double EPS = 1e-9; 35 36 /* 37 #include <ext/pb_ds/assoc_container.hpp> 38 #include <ext/pb_ds/tree_policy.hpp> 39 40 using namespace __gnu_pbds; 41 tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T; 42 */ 43 44 int T, n, m, u, v, c; 45 map<pii, int> mmp; 46 struct edge { 47 int v, c; 48 edge () {} 49 edge (int v, int c) : v(v), c(c) {} 50 bool operator < (const edge &e) const { 51 return c < e.c;} 52 }; 53 vector<edge> E[2015]; 54 ll spfa(int &flag) { 55 bool in_que[2015]; 56 ll dis[2015]; 57 int cnt[2015]; 58 59 clr(in_que, 0); 60 clr(cnt, 0); 61 for (int i = 1; i <= n; ++i) { 62 dis[i] = 1e18; 63 } 64 dis[0] = 0; 65 deque<int> que; 66 que.push_front(0); 67 68 while (que.size()) { 69 int x = que.front(); que.pop_front(); 70 in_que[x] = 0; 71 for (int i = 0; i < E[x].size(); ++i) { 72 int v = E[x][i].v, c = E[x][i].c; 73 if (dis[v] > dis[x] + c) { 74 dis[v] = dis[x] + c; 75 if (!in_que[v]) { 76 if (que.size() && dis[v] < dis[que.front()] + 1) { 77 que.push_front(v); 78 } else { 79 que.push_back(v); 80 } 81 in_que[v] = 1; 82 cnt[v] = cnt[x] + 1; 83 if (n < cnt[v]) { 84 flag = 1; 85 return 2333; 86 } 87 } 88 } 89 } 90 } 91 92 ll ans = 1e18; 93 for (int i = 1; i <= n; ++i) { 94 ans = min(ans, dis[i]); 95 } 96 return ans; 97 } 98 int main() { 99 scanf("%d", &T); 100 while (T--) { 101 scanf("%d%d", &n, &m); 102 mmp.clear(); 103 int mi = 1e18; 104 for (int i = 1; i <= m; ++i) { 105 scanf("%d%d%d", &u, &v, &c); 106 if (mmp.count(pii(u, v))) { 107 int x = mmp[pii(u, v)]; 108 c = min(x, c); 109 } 110 mmp[pii(u, v)] = c; 111 mi = min(mi, c); 112 } 113 if (mi >= 0) { 114 printf("%d ", mi); 115 continue; 116 } 117 for (int i = 1; i <= n; ++i) E[i].clear(); 118 for (map<pii, int>::iterator it = mmp.begin(); it != mmp.end(); ++it) { 119 int u = (*it).first.first, v = (*it).first.second, c = (*it).second; 120 E[u].pb(edge(v, c)); 121 } 122 for (int i = 1; i <= n; ++i) { 123 E[0].pb(edge(i, 0)); 124 } 125 for (int i = 0; i <= n; ++i) { 126 sort(E[i].begin(), E[i].end()); 127 } 128 int flag = 0; 129 ll ans = spfa(flag); 130 if (flag) { 131 puts("-inf"); 132 } else { 133 printf("%lld ", ans); 134 } 135 } 136 return 0; 137 }