[luoguP3953] 逛公园（DP + spfa）传送门看到求方案数，应该很容易想到dpf[u][i]表示到点u，且比到u的最短距离多i的方案数那么需要先预处理dis数组，spfa或者堆优化的dijk因为考虑到dp的顺序，f[u][i]转移到f[v][j]
[BZOJ2118] 墨墨的等式（最短路）传送门好神啊。。需要用非负数个a1,a2,a3...an来凑出B可以知道，如果一个数x能被凑出来，那么x+a1，x+a2.......x+an也都能被凑出来那么我们只需要选择a1~an中任意一个的a，可以求出
[BZOJ4992] [Usaco2017 Feb]Why Did the Cow Cross the Road（spfa）传送门把每个点和曼哈顿距离距离它3步或1步的点连一条边，边权为3 * t + a[x][y]因为，走3步，有可能是3步，也有可能是1步（其中一步拐了回来）最后，把终点和曼哈顿距离距离它1步和2布的
[BZOJ1663] [Usaco2006 Open]赶集（spfa最长路）传送门按照时间t排序如果 t[i] + map[i][j] <= t[j]，就在i和j之间连一条边然后spfa找最长路#include <queue>#include <cstdio>#include <cstring>#include <iostream>#inclu
[luoguP3110] [USACO14DEC]驮运Piggy Back（SPFA || BFS）传送门
以 1，2，n 为起点跑3次 bfs 或者 spfa
那么 ans = min(ans, dis[1][i] * B + dis[2][i] * E + dis[3][i] * P) (1 <= i <= n)
#include <queue>
#include <cstdio>
[luoguP1849] [USACO12MAR]拖拉机Tractor（spfa）传送门
神奇的spfa
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 1010
#define max(x, y) ((x) > (y) ? (x) : (y))
int n,
[luoguP1772] [ZJOI2006]物流运输（DP + spfa）传送门
预处理cost[i][j]表示从第i天到第j天起点到终点的最短距离
f[i]表示前i天到从起点到终点的最短距离
f[0] = K
f[i] = min(f[i], f[j 1] + cost[j][i] + K)
#inc
[luoguP2622] 关灯问题II（状压最短路）传送门
本以为是状压DP，但是有后效性。
所以写一手状压spfa
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 11
#define M 101
[luoguP3275] [SCOI2011]糖果（差分约束）传送门
差分约束裸题
但是坑！
有一个点是长为10W的链，需要逆序加边才能过（真是玄学）
还有各种坑爹数据
开longlong
——代码
1 #include <cstdio>
2 #include <cstring>
[luoguP1993] 小 K 的农场（差分约束 + spfa 判断负环）传送门
差分约束系统。。找负环用spfa就行
——代码
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #define N 100001
5
6 int n, m, cnt
[CODEVS1912] 汽车加油行驶问题（分层图最短路）传送门
吐槽：神tm网络流
dis[i][j][k] 表示到 (i, j) 还有 k 油的最优解
然后跑spfa，中间分一大堆情况讨论
1.当前队头还有油
1.目标点有加油站——直接过去
2.目
[CODEVS1911] 孤岛营救问题（分层图最短路）传送门
吐槽：神tm网络流。。。
用持有的钥匙分层，状态压缩，用 2 进制表示持有的钥匙集合。
dis[i][j][k] 表示持有的钥匙集合为 k，到达点 (i, j) 的最短路径。
分层图的最短
[luoguP2761] 软件补丁问题（状压最短路）传送门
n <= 20 很小
所以可以状态压缩
然后因为可能存在环，所以不能DP
那么就用spfa找最短路
被位运算坑了，不清楚优先级一定要加括号
——代码
1 #include <queue>
[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）传送门
题意
N个点M条边的有向图
每个点有点权
从某一个结点出发
问能获得的最大点权和
一个点的点权最多被计算一次
N<=500000 M<=500000
思路
先tarjan缩点，然后就形成
[luoguP1186] 玛丽卡（spfa）传送门
因为要随机删除一条边，而枚举所有边肯定会超时，经过发现，先求出一遍最短路，而要删除的边肯定在最短路径上，删除其他的边对最短路没有影响。
所以可以先求出最短路，再枚举
[luoguP1266] 速度限制（spfa）传送门
因为到某一没有限速的路径速度会有不同的可能，所以直接用 dis[i][j] 表示到第 i 个点速度为 j 时的最短时间，然后跑spfa。
——代码
1 #include <queue>
2 #inc
[POJ1797] Heavy Transportation（最大生成树 || 最短路变形）传送门
1.最大生成树
可以求出最大生成树，其中权值最小的边即为答案。
2.最短路
只需改变spfa里面的松弛操作就可以求出答案。
——代码
1 #include <queue>
负环传送门
来自题解：luogu/wiki/show?name=题解+P3385
1.BellmanFord
通过BelmanFord求出最短路，然后在进行一遍松弛操作，如果可以再松弛说明存在负环，否则不存在。
2.SPFA
SPF
NOIP2009T3最优贸易（Dfs + spfa）洛谷传送门
看到这个题，原本想先从后往前dfs，求出能到终点的点，再在这些点里从前往后spfa，用一条边上的两个城市的商品价格的差来作边权，实施过后，发现图中既有负边权，又有回路，以
【模板】链式前向星+spfa洛谷传送门——分糖果
博客——链式前向星
团队中一道题，数据很大，只能用链式前向星存储，spfa求单源最短路。
可做模板。
#include <cstdio>
#include <queue>
#include <c
