关于SPFA它死了，它又复活了
一切的一切还是源自这道题：P3275 [SCOI2011] 糖果 - 洛谷
这道题本是可用 SPFA 过的，但是出题人加了一些卡 SPFA 的数据，因此 TLE 了。但是我在求助区看到了这位大佬的优化，我才明白：SPFA它又复活了
其实思路很简单。卡 SPFA 的数据是使用了特殊的建图方式，使图比较特殊。那么我们在建图时也可以随机建图。事实证明，非常有用。
根据大佬的思路，需要用随机种子 random_device，随机函数 mt19937，以及打乱容器顺序函数 shuffle。由于这道题要用最长路，自然应该让长度长的先进队列。
这是我的 P3275 的代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
typedef long long ll;
struct edge{
ll to, next, w;
}e[maxn << 1];
ll d[maxn], head[maxn], len, n, m, cnt[maxn];
bool vis[maxn];
deque<ll>q;
inline void Spfa(ll s){
q.push_back(s);
d[s] = 0;
vis[s] = 1;
while(!q.empty()){
ll u = q.front();
vis[u] = 0;
q.pop_front();
for(ll i = head[u]; i; i = e[i].next){
ll v = e[i].to;
if(d[v] < d[u] + e[i].w){
d[v] = d[u] + e[i].w;
cnt[v] = cnt[u] + 1;
if(cnt[v] > n){
cout << "-1" << endl;
return;
}
if(!vis[v]){
vis[v] = 1;
if(!q.empty() && d[u] + e[i].w >= d[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
ll ans = 0;
for(int i = 1; i <= n; ++i)
ans += d[i];
cout << ans << endl;
}
inline void insert(ll u, ll v, ll w){
e[++len].to = v;
e[len].w = w;
e[len].next = head[u];
head[u] = len;
}
inline void solve(){
ios::sync_with_stdio(0);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
ll beg = n + 1;
for(ll i = 0; i <= beg; ++i)
d[i] = -0x3f3f3f3f;
for(ll i = 1; i <= m; ++i){
ll a, b, c;
cin >> c >> a >> b;
if(c == 1)
insert(a, b, 0), insert(b, a, 0);
else if(c == 2)
insert(a, b, 1);
else if(c == 3)
insert(b, a, 0);
else if(c == 4)
insert(b, a, 1);
else
insert(a, b, 0);
if(a == b && (c == 2 || c == 4)){
printf("-1\n");
return;
}
}
vector<ll>nice;
for(ll i = 1; i <= n; ++i)
nice.push_back(i);
random_device send; //制造一个随机种子
mt19937 f(send()); //根据随机种子建立随机函数
shuffle(nice.begin(), nice.end(), f); //打乱容器
for(auto i : nice) //随机化建图
insert(0, i, 1);
Spfa(0);
}
int main(){
solve();
return 0;
}