最短路文章列表
[luoguP1266] 速度限制（spfa）
传送门 因为到某一没有限速的路径速度会有不同的可能，所以直接用 dis[i][j] 表示到第 i 个点速度为 j 时的最短时间，然后跑spfa。 ——代码 1 #include queue 2 #in...最短路,spfa
[luoguP1186] 玛丽卡（spfa）
传送门 因为要随机删除一条边，而枚举所有边肯定会超时，经过发现，先求出一遍最短路，而要删除的边肯定在最短路径上，删除其他的边对最短路没有影响。 所以可以先求出最短路，再枚举删除最短路上的每一条边再求最...最短路,spfa
[luoguP1027] Car的旅行路线（Floyd）
传送门 建图麻烦，建完图搞一遍Floyd就好了。 ——代码 1 #include iostream 2 #include cstdio 3 #include cmath 4 5 using names...最短路,Floyd
[luoguP1119] 灾后重建（Floyd）
传送门 基于Floyd的动态规划原理，我们可以只用进行一次Floyd。 而题目给出的限制条件相当于给Floyd加了时间限制而已。 还是得靠对Floyd的理解。 ——代码 1 #include cstd...最短路,Floyd
[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
NOIP2014D2T2寻找道路（Spfa）
洛谷传送门 这道题可以把边都反着存一遍，从终点开始深搜，然后把到不了的点 和它们所指向的点都去掉。 最后在剩余的点里跑一遍spfa就可以了。 ——代码 #include cstdio#include ...最短路
【模板】Dijkstra的heap优化
为了将最小费用最大流的spfa优化，决定将spfa换成heap优化的Dijkstra。（dijkstra不能处理负边权） 所以还得现学。。。 白点表示已经确定最短路径的点。 蓝点表示还未确定最短路径的...最短路,stl,堆,模板,dijkstra
【模板】链式前向星+spfa
洛谷传送门——分糖果 博客——链式前向星 团队中一道题，数据很大，只能用链式前向星存储，spfa求单源最短路。 可做模板。 #include cstdio#include queue#include ...模板,最短路,spfa
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化