这是两个月前的一个帖子，他使用随机打乱的方法让SPFA复活。

今天学了差分约束，这是一道练习题。正常SPFA80pts，经过玄学优化可以AC。

代码如下

#include <bits/stdc++.h>
using namespace std;
int n,k,opt,a,b;
struct edge{int t,w;};
vector<edge> e[100005];
queue<int> q; bool inq[100005];
long long dis[100005],cnt[100005];
edge make_edge(int t, int w)
{
	edge s; s.t=t; s.w=w;
	return s;
}
bool spfa()
{
	for (int i=1; i<=n; i++)
	{
		dis[i]=-100000000;
	}
	dis[0]=1;
	inq[0]=1; cnt[0]=1; q.push(0);
	while (!q.empty())
	{
		int k=q.front(); q.pop(); inq[k]=0;
		for (int i=0; i<e[k].size(); i++)
		{
			if (dis[e[k][i].t]<dis[k]+e[k][i].w)
			{
				dis[e[k][i].t]=dis[k]+e[k][i].w;
				if (!inq[e[k][i].t])
				{
					inq[e[k][i].t]=1;
					cnt[e[k][i].t]+=rand()%(n/2)+1;
					q.push(e[k][i].t);
					if (cnt[e[k][i].t]>=n+1 && cnt[e[k][i].t]<=n+2)
					{
						return 1;
					}
				}
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d %d",&n,&k);
	for (int i=1; i<=k; i++)
	{
		scanf("%d %d %d",&opt,&a,&b);
		if (opt==1)
		{
			e[a].push_back(make_edge(b,0));
			e[b].push_back(make_edge(a,0));
		}
		else if (opt==2)
		{
			e[a].push_back(make_edge(b,1));
		}
		else if (opt==3)
		{
			e[b].push_back(make_edge(a,0));
		}
		else if (opt==4)
		{
			e[b].push_back(make_edge(a,1));
		}
		else
		{
			e[a].push_back(make_edge(b,0));
		}
	}
	for (int i=1; i<=n; i++)
	{
		e[0].push_back(make_edge(i,0));
	}
	if (spfa())
	{
		cout<<-1;
	}
	else
	{
		long long ans=0;
		for (int i=1; i<=n; i++)
		{
			ans+=dis[i];
		}
		cout<<ans;
	}
	return 0;
}

其中唯一与正常SPFA有区别的地方在这里

cnt[e[k][i].t]+=rand()%(n/2)+1;

其中 cnt 为记录入队次数的数组。正常来说应该是 ++，但这里改为 +=rand()%(n/2)+1。

同时注意到我没有写srand，因此随机数序列固定，是稳定的100pts，不会发生评测波动。