[SPFA]SLF+LLL优化

[原帖地址](http://blog.csdn.net/oranges\_c/article/details/64124235) 记下SPFA的两种优化，大牛请无视 SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j) < dist(i)，则将j插入队首，否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，每次弹出时进行判断，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。 ```cpp char str[maxn][maxn]; int vis[maxn][maxn],dis[maxn][maxn],n,m; int ans[30],sum,cnt; int dx[] = {-1,-1,0,1,1,1,0,-1},dy[] = {0,1,1,1,0,-1,-1,-1}; deque<PII>q; void spfa() { while(!q.empty()){ PII f = q.front();q.pop_front(); //LLL优化 if(dis[f.fi][f.se] * cnt > sum){ q.push_back(f); continue; } sum -= dis[f.fi][f.se];cnt--; vis[f.fi][f.se] = 0; for( int i = 0; i < 8; i++ ){ int nx = f.fi + dx[i],ny = f.se + dy[i]; if(nx < 1 || nx > n || ny < 1 || ny > m)continue; int w = (str[nx][ny] != str[f.fi][f.se]); if(dis[nx][ny] > dis[f.fi][f.se] + w){ dis[nx][ny] = dis[f.fi][f.se] + w; if(!vis[nx][ny]){ vis[nx][ny] = 1; //SLF优化 if(dis[nx][ny] < dis[q.front().fi][q.front().se]){ q.push_front(mp(nx,ny)); } else { q.push_back(mp(nx,ny)); } sum += dis[nx][ny];cnt++; } } } } } void init() { cl(dis,INF); cl(vis,0); cl(ans,INF); sum = cnt = 0; } ```