[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
[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））传送门
蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。
首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径
因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs
[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>
[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）传送门
因为答案满足单调性，所以看到这个题，第一反应是二分，但是总是WA，也没有超时。
看了题解，，，，，，
这题刚开始很多人会想到二分，二分答案，然后看看是否能绕过所有信号塔，但是，这样
[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
[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>
[POJ3463] Sightseeing（次短路 Heap + Dijkstra）传送门
用dijkstra比较好，spfa可能有的重复
dis[x][2]:dis[x][0]表示起点到x的最短路、dis[x][1]表示起点到x的次短路；
tot[x][2]:tot[x][0]表示起点到x的最短路条数、tot[x
[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）传送门
题意
N个点M条边的有向图
每个点有点权
从某一个结点出发
问能获得的最大点权和
一个点的点权最多被计算一次
N<=500000 M<=500000
思路
先tarjan缩点，然后就形成
[luoguP1266] 速度限制（spfa）传送门
因为到某一没有限速的路径速度会有不同的可能，所以直接用 dis[i][j] 表示到第 i 个点速度为 j 时的最短时间，然后跑spfa。
——代码
1 #include <queue>
2 #inc
[luoguP1186] 玛丽卡（spfa）传送门
因为要随机删除一条边，而枚举所有边肯定会超时，经过发现，先求出一遍最短路，而要删除的边肯定在最短路径上，删除其他的边对最短路没有影响。
所以可以先求出最短路，再枚举
[luoguP1027] Car的旅行路线（Floyd）传送门
建图麻烦，建完图搞一遍Floyd就好了。
——代码
1 #include <iostream>
2 #include <cstdio>
3 #include <cmath>
4
5 using namespace std;
6
7 int n,
[luoguP1119] 灾后重建（Floyd）传送门
基于Floyd的动态规划原理，我们可以只用进行一次Floyd。
而题目给出的限制条件相当于给Floyd加了时间限制而已。
还是得靠对Floyd的理解。
——代码
1 #include
[POJ1797] Heavy Transportation（最大生成树 || 最短路变形）传送门
1.最大生成树
可以求出最大生成树，其中权值最小的边即为答案。
2.最短路
只需改变spfa里面的松弛操作就可以求出答案。
——代码
1 #include <queue>
负环传送门
来自题解：luogu/wiki/show?name=题解+P3385
1.BellmanFord
通过BelmanFord求出最短路，然后在进行一遍松弛操作，如果可以再松弛说明存在负环，否则不存在。
2.SPFA
SPF
【模板】Dijkstra的heap优化为了将最小费用最大流的spfa优化，决定将spfa换成heap优化的Dijkstra。（dijkstra不能处理负边权）
所以还得现学。。。
白点表示已经确定最短路径的点。
蓝点表示还未确定最短路
NOIP2009T3最优贸易（Dfs + spfa）洛谷传送门
看到这个题，原本想先从后往前dfs，求出能到终点的点，再在这些点里从前往后spfa，用一条边上的两个城市的商品价格的差来作边权，实施过后，发现图中既有负边权，又有回路，以
NOIP2014D2T2寻找道路（Spfa）洛谷传送门
这道题可以把边都反着存一遍，从终点开始深搜，然后把到不了的点 和它们所指向的点都去掉。
最后在剩余的点里跑一遍spfa就可以了。
——代码
#include <cstdio>
【模板】链式前向星+spfa洛谷传送门——分糖果
博客——链式前向星
团队中一道题，数据很大，只能用链式前向星存储，spfa求单源最短路。
可做模板。
#include <cstdio>
#include <queue>
#include <c
