spfa文章列表
[CODEVS1912] 汽车加油行驶问题（分层图最短路）
传送门 吐槽：神tm网络流 dis[i][j][k] 表示到 (i, j) 还有 k 油的最优解 然后跑spfa，中间分一大堆情况讨论 1.当前队头还有油 1.目标点有加油站——直接过去 2.目标点每...最短路,spfa
[CODEVS1911] 孤岛营救问题（分层图最短路）
传送门 吐槽：神tm网络流。。。 用持有的钥匙分层，状态压缩，用 2 进制表示持有的钥匙集合。 dis[i][j][k] 表示持有的钥匙集合为 k，到达点 (i, j) 的最短路径。 分层图的最短路听...最短路,spfa
[luoguP2761] 软件补丁问题（状压最短路）
传送门 n = 20 很小 所以可以状态压缩 然后因为可能存在环，所以不能DP 那么就用spfa找最短路 被位运算坑了，不清楚优先级一定要加括号 ——代码 1 #include queue 2 #in...spfa,最短路
[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）
传送门 题意 N个点M条边的有向图 每个点有点权 从某一个结点出发 问能获得的最大点权和 一个点的点权最多被计算一次 N=500000 M=500000 思路 先tarjan缩点，然后就形成一个dag...DP,最短路,dfs,spfa,stl
[luoguP1266] 速度限制（spfa）
传送门 因为到某一没有限速的路径速度会有不同的可能，所以直接用 dis[i][j] 表示到第 i 个点速度为 j 时的最短时间，然后跑spfa。 ——代码 1 #include queue 2 #in...最短路,spfa
[luoguP1186] 玛丽卡（spfa）
传送门 因为要随机删除一条边，而枚举所有边肯定会超时，经过发现，先求出一遍最短路，而要删除的边肯定在最短路径上，删除其他的边对最短路没有影响。 所以可以先求出最短路，再枚举删除最短路上的每一条边再求最...最短路,spfa
[POJ1797] Heavy Transportation（最大生成树 || 最短路变形）
传送门 1.最大生成树 可以求出最大生成树，其中权值最小的边即为答案。 2.最短路 只需改变spfa里面的松弛操作就可以求出答案。 ——代码 1 #include queue 2 #include c...最小生成树,最短路,spfa
负环
传送门 来自题解：luogu/wiki/show?name=题解+P3385 1.BellmanFord 通过BelmanFord求出最短路，然后在进行一遍松弛操作，如果可以再松弛说明存在负环，否则不...模板,spfa,负环,最短路,Bellman-Ford
NOIP2009T3最优贸易（Dfs + spfa）
洛谷传送门 看到这个题，原本想先从后往前dfs，求出能到终点的点，再在这些点里从前往后spfa，用一条边上的两个城市的商品价格的差来作边权，实施过后，发现图中既有负边权，又有回路，以及各种奇奇怪怪的东...最短路,spfa,dfs
【模板】链式前向星+spfa
洛谷传送门——分糖果 博客——链式前向星 团队中一道题，数据很大，只能用链式前向星存储，spfa求单源最短路。 可做模板。 #include cstdio#include queue#include ...模板,最短路,spfa
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化