SPFA及其优化---他复活了
SPFA算是一种比较万能的最短路算法了
时间复杂度：O（mn）
特点：
1.每个点可以入队多次
2.不能处理负环，但可以判断负环
3.队列优化减少一些冗余的松弛操作
贴一个模板题http://www.acmicpc.sdnu.edu.cn/problem/show/1223
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
struct node
{
int y,z,next;
}t[1000000];
int n,m,tot,a,b,c;
bool v[10000];
int d[10000],head[10000],times[10000];
void init()
{
for(int i = 1;i <= n; ++i)
{
d[i] = 1e9; //统计起点开始到各点的最短路径
v[i] = 0; //标记是否在队列中
head[i] = -1;
times[i] = 0; //入队次数，用以判断负环
}
}
void add(int x,int y,int z)
{
t[++tot].y = y;
t[tot].z = z;
t[tot].next = head[x];
head[x] = tot;
}
bool spfa(int start)
{
queue<int>q;
d[start] = 0;
v[start] = 1;
q.push(start);
times[start] = 0;
while(!q.empty())
{
int now = q.front();
q.pop();
v[now] = 0; //记得把now的标记去掉才能再次入队
for(int i = head[now];i != -1;i = t[i].next)
{
if(d[t[i].y] > d[now] + t[i].z)
{
d[t[i].y] = d[now] + t[i].z;
if(!v[t[i].y])
{
v[t[i].y] = 1;
q.push(t[i].y);
if(++times[t[i].y] > n) return 0;
}
}
}
}
return 1;
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
init();
for(int i = 1;i <= m; ++i)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
if(spfa(1))printf("%d\n",d[n]);
else printf("IMPOSSIBLE!\n");
}
return 0;
}
当然这只是朴素的SPFA，做题中有好多题是专门用来卡SPFA的（有点惨哦）
所以可以加优化
SLF 双端队列 极值优化：即将入队的点dist(i)若比队头元素dist(j)大，就从后面入队，否则从前面入队
LLF 平均值优化：队列中所有dist值的平均值为x，若即将入队的点dist(i)>x则将i插入到队尾，否则从前面入队
优先队列优化：每次入队都从小到大自动排序，看起来每次都选取最优的，但实际每次都要维护队列，也增加了一些不必要的操作，复杂度并不敢保证
还是这个题http://www.acmicpc.sdnu.edu.cn/problem/show/1223
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
struct node
{
int y,z,next;
}t[1000000];
int n,m,tot,a,b,c,sum,ts;
bool v[10000];
int d[10000],head[10000],times[10000];
void init()
{
for(int i = 1;i <= n; ++i)
{
d[i] = 1e9;
v[i] = 0;
head[i] = -1;
times[i] = 0;
}
sum = 0;
}
void add(int x,int y,int z)
{
t[++tot].y = y;
t[tot].z = z;
t[tot].next = head[x];
head[x] = tot;
}
bool spfa(int start)
{
deque<int>q;
d[start] = 0;
v[start] = 1;
q.push_front(start);
times[start] = 0;
sum += start; ts = 1;
while(!q.empty())
{
int now = q.front();
q.pop_front();
v[now] = 0;
sum -= d[now];
ts--;
for(int i = head[now];i != -1;i = t[i].next)
{
if(d[t[i].y] > d[now] + t[i].z)
{
d[t[i].y] = d[now] + t[i].z;
if(!v[t[i].y])
{
v[t[i].y] = 1;
if(q.empty() || d[t[i].y] > d[q.front()] || d[t[i].y] * ts > sum)
q.push_back(t[i].y);
//如果队列为空进行q.front()会出错
else
q.push_front(t[i].y);
sum += d[t[i].y];
if(++times[t[i].y] > n) return 0;
}
}
}
}
return 1;
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
init();
for(int i = 1;i <= m; ++i)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
if(spfa(1))printf("%d\n",d[n]);
else printf("IMPOSSIBLE!\n");
}
return 0;
}
