基础部分完成接下来是稍微进阶一点的东西

今天讲的有关最短路算法spfa：

SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)。

但是对于比赛这种东西，长期以来有一个结论：

所以我们今天来鞭个尸

如何卡spfa

首先了解一下spfa有哪些算法上的漏洞。

Spfa每次取出队头元素，处理和它相邻的点，如果说dis(最短路数组)更新，则将此元素加入队列，如此循环直到没法再更新dis数组。

如果我们整个特殊的图，使得这个元素刚刚被取出，就被下一个元素入队，那么总共的入队次数，就会被卡到。。。很大很大的数。。。

所以这个图应该是什么样呢？

菊花图中长条链。

从1节点到每个节点都连一条边，节点编号越大则这条边权越小，使得从最后一个节点开始一直更新下一个节点的dis数组。这是菊花图。

再从最后一个节点开始向编号小一的节点连一条边权很小的边，这条边用来使接下来的节点被反复更新。

直接代码干脆利落：

#include<bits/stdc++.h>

using namespace std;

int main(){

int seed;

seed=time(NULL);

srand(seed);

int n=rand()%1000,m=n*2-2;

printf("%d %d\n&#​34;,n,m);

for(int i=n;i>=2;--i)

printf("1 %d %d\n%d %d 1\n&#​34;,i,(n-i+1)*2+1,i,i-1);

}