SPFA
由最短路算法2中我们可以看到Dijkstra算法并不能帮助我们判断负环（事实上如果用某些模板有负边权就会出错），这时候我们就需要用到SPFA算法了。
SPFA算法的思路是队列优化，用一个dis数组计算从源点到每个点的最短路，对于这n个点，m条边，我们从源点出发，搜索从这个点出发的所有边能到达的点，看是否可以更新dis数组，若可以更新，判断该点并有没有在队列中，若不在，则将这个点添加到队列中，并且将这个点进队的次数加一，显然对于一个点，它的最好情况就是每个点都可以更新它所在的dis，因此它的进队次数不应该超过n次，否则证明出现了负环。
例题：https://www.luogu.org/problem/P2648
赚钱
zzy现在决定环游中国，顺便赚点钱。zzy在一个城市最多只能赚D元，然后他可以选择退休也就是停止赚钱，或者去其它城市工作。当然，他可以在别处工作一阵子后又回到原来的城市再赚D元。这样的往返次数是没有任何限制的。
城市间有P条单向路径连接，共有C座城市，编号从1到C。路径i从城市Ai到城市Bi，在路径行走上不用任何花费。
zzy还可以乘飞机从某个城市飞到另一个城市。共有F条单向的航线，第i条航线是从城市Ji飞到另一座城市Ki，费用是Ti元。假如zzy身上没有现钱，他可以用以后赚的钱来付机票钱。
zzy可以从任何一个城市出发开始赚钱，并且选择在任何时候、任何城市退休。现在zzy想要知道，如果在工作时间上不做限制，那么zzy共可以赚多少钱呢？如果赚的钱也不会出现限制，那么就输出orz。
输入格式
第一行，4个用空格分开的正整数，D，P，C，F。
第二行到P+1行，第i+1行包含2个用空格分开的整数，表示一条从城市Ai到城市Bi的单向路径。
接下来的F行，每行3个用空格分开的正整数，表示一条从城市Ji到城市Ki的单向航线，费用为Ti。
输出格式
如果zzy赚的钱没有限制，输出orz。如果有限制，那么就输出在给定的规则下zzy最多可以赚到的钱数。
输入输出样例
输入 复制
100 3 5 2
1 5
2 3
1 4
5 2 150
2 5 120
输出 复制
250
AC代码：
#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
int to,pow,next;
}map[100005];
int find[100005];
int cnt;
int d,p,c,f;
void build(int from,int to,int cost)
{
map[++cnt].to = to;
map[cnt].pow = cost -d;
map[cnt].next = find[from];
find[from] = cnt;
}
int vis[100005];
int num[100005];
int dis[100005];
int main()
{
memset(find,-1,sizeof(find));
queue<int>q;
scanf("%d%d%d%d",&d,&p,&c,&f);
int x,y;
for(int i = 0;i<p;i++)
{
scanf("%d%d",&x,&y);
build(x,y,0);
}
int cost;
for(int i = 0;i <f;i++)
{
scanf("%d%d%d",&x,&y,&cost);
build(x,y,cost);
}
int min = INF;
for(int i = 1;i <= c;i++)
{
memset(vis,0,sizeof(vis));
memset(num,0,sizeof(num));
memset(dis,0x3f,sizeof(dis));
dis[i] = -d;
vis[i] = 1;
num[i]++;
q.push(i);
while(!q.empty())
{
int p = q.front();
q.pop();vis[p] = 0;
int t = find[p];
while(t != -1)
{
if(dis[p] + map[t].pow< dis[map[t].to])
{
dis[map[t].to] = dis[p] + map[t].pow;
if(vis[map[t].to] == 0)
{
q.push(map[t].to);
vis[map[t].to] = 1;
num[map[t].to]++;
if(num[map[t].to] > c)
{
printf("orz\n");
return 0;
}
}
}
t = map[t].next;
}
}
for(int k = 1;k <=c;k++)
if(min > dis[k])
min = dis[k];
}
printf("%d\n",-min);
}
超级源：
在某些题目中（如上例题），会出现求多个点到多个点的最短路，这种情况下肯定最先想到用Floyed算法，但是复杂度达到了O（n^3），Dijkstra和spfa算法都是单源最短路，要用只能使用n次，复杂度同样很高,这种情况我们可以建立一个超级源，即新建一个节点，它到每个点的边权都为0.以超级源作为起始点使用Dijkstra和spfa算法即可解决问题
