NOI2018 Day1 T1有许多人用spfa被卡掉25分。
注意：写spfa绝对不用STL，因为出题人会不怀好意的卡掉它。
我也是愿意写spfa的人.(毕竟简单)。在这里总结一下spfa的优化
1.普通spfa会开一个数组。可以用循环队列优化.(教程书中都有).
2.我们在把点加入队列时,随机从队首或队尾加入(几乎没人会卡掉)。
如果嫌麻烦，可以开成栈。
3.设要加入的节点是j，队首元素为i，若dist(j) < dist(i)，则将j插入队首，否则插入队尾。
4.设队首元素为i，每次弹出时进行判断，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。
这几种方法选一种或两种就够了。
普通spfa就不说了。
负环就是在普通spfa上加一句话，若扩展的点已经被扩展n次就说明有负环了。
题目:VIJOS P1053 Easy sssp
代码如下：
#include<cstdio>
#include<cstring>
#define N 101000
int n,m,s;
int to[N];
int head[N];
int nex[N];
int val[N];
int f[N];
int que[N];
int cnt[N];
int is[N];
int inq[N];
int a,b,c,idx;
void push(int &x)
{
x++;
if(x==N)
x=1;
}
void addedge(int a,int b,int c)
{
nex[++idx]=head[a];
head[a]=idx;
to[idx]=b;
val[idx]=c;
}
bool spfa(int s)
{
for(int i=1;i<=n;i++)
inq[i]=0,cnt[i]=0,f[i]=0x3f3f3f3f;
f[s]=0;
cnt[s]=1;
inq[s]=1;
int front=0,tail=0;
que[tail]=s;
push(tail);
while(front!=tail)
{
int idx1=que[front];
push(front);
inq[idx1]=0;
for(int i=head[idx1];i;i=nex[i])
{
if(f[to[i]]>f[idx1]+val[i])
{
f[to[i]]=f[idx1]+val[i];
if(!inq[to[i]])
{
inq[to[i]]=1;
que[tail]=to[i];
push(tail);
cnt[to[i]]++;//记录入队次数
if(cnt[to[i]]>n)
return 0;
}
}
}
}
return 1;
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(a==b&&c<0)
{
puts("-1");
return 0;
}
if(a!=b)
addedge(a,b,c);
}
memset(f,0x3f,sizeof(f));
memset(que,0,sizeof(que));
int maxn=n+1;//建一个空节点,用这个点跑spfa
for(int i=1;i<=n;i++)
addedge(maxn,i,0);
if(!spfa(maxn))
{
puts("-1");
return 0;
}
spfa(s);
for(int i=1;i<=n;i++)
{
if(f[i]>=0x3f3f3f3f)
printf("NoPath\n");
else
printf("%d\n",f[i]);
}
return 0;
}