原创于2017.04.03：最短路1.多源的Floyd,邻接矩阵实现，复杂度O（n^3），n<400;2.单源Dijkstra，邻接矩阵实现，无负边，复杂度O（n^2），n<10000；3.单源Dijkstra，邻接表实现，堆优化，无负边，复杂度O（ElogE），点多边少；4.单源bellman_ford，边集实现，可验负环，复杂度O（nE），nm<10^8；5.单源SPFA，邻接表+队列实现，可验负环

  clc;clear;%定义边列表（源节点，目标节点，权重）w1=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];s1=[1,1,1,1,1,1,2,2,2,2,3,3,3,3,3,3,3,4,5,6,7,7,8,9,10,10,10,11,11,11,12,13,14,14,15,15,15,16,17,18,

2024.6.16挑了套简单ABC找找状态，做了E、F、G。E稍微思考一下会发现有用的量是每种字母选的个数，记第$i$种字母用了$a_i$个，那么答案就是$\binom{n}{a_1}\binom{n-a_1}{a_2}\binom{n-a_1-a_2}{a_3}...\binom{n-a_1-a_2-...-a_{n-1}}{a_n}$。化简一下就是

描述一个无向连通图，每个点\(u\)有点权\(w_u\)，处在\(u\)点时可以花费\(w_u\)的时间去任何一个距离\(u\)最短路径边数不超过\(f_u\)的点。现在，从\(1\)号点出发，对于每个\(1\lek\len\)，求出\(1\)到\(k\)需要的最小时间。\(n\leq200000\)\(m\leqn+50\)解决

原题链接：https://www.luogu.com.cn/problem/P5663题意解读：工人是图中的点，传送带是图中的无向边，给出q个询问a,l，判断是否能有一条1号点到a点的路径为l。解题思路：考试的关键是拿分！同样可以来面向数据编程：1、测试点 1∼4，1≤

最短路系列：Dijkstra算法大家好，我是Weekoder!最短路系列的第二期：Dijkstra他来啦！那么废话不多说，让我们直奔主题吧。Dijkstra算法的用处与floyd算法不同的，Dijkstra算法用于求解单源最短路径。顾名思义，单源最短路径就是起点唯一，终点有多个的最短路算法。Dijkstra的思想是

最短路系列：floyd算法大家好，我是Weekoder!最近学了最短路，我来出一个最短路系列辣！今天的算法是：floyd算法！我会用我自己的理解尽量让大家搞懂floyd算法。floyd算法的用处floyd算法是最短路算法之一，适合求解多源最短路径问题。什么是多源最短路径呢？其实就是起点和终点都有

最短路系列：SPFA算法大家好，我是Weekoder！终于，我们的最短路算法SPFA闪亮登场了！虽然话是这么说，但是我还是建议大家先学习Dijkstra算法，再来学习SPFA。并且我们在这里学习的SPFA算法只能通过P3371，并不能通过标准版的P4779。SPFA的原型——Bellman-Ford在学习SPFA之前，我

目录朴素dijkstra算法——模板题AcWing849.Dijkstra求最短路I题目代码堆优化版dijkstra——模板题AcWing850.Dijkstra求最短路II题目代码Bellman-Ford算法——模板题AcWing853.有边数限制的最短路题目代码spfa算法（队列优化的Bellman-Ford算法）——

dijkstraCode：#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>pii;constintN=1e5+5,inf=INT_MAX;intn,m,dis[N],s;//structnode{//intfrom,to,w,val;//};boolvis[N];vector<pii>edge

一个比较重要的性质：反转的边要在最短路上才会有贡献。我们可以先跑一遍最短路，记录下整颗最短路树，然后暴力的对每一条边进行判断，反转。我们建正反图各两个，分别以\(1\)，\(n\)为起点。\(n\)，\(1\)为终点。然后对每个图跑最短路，记录下最短路树。若不反转任何一条边，则答案为\(1\)

迪杰斯特拉(dijkstra)////CreatedbyLANSGANBSon2024/3/8.///**codetemplate:https://github.com/LANSGANBS/code-template*URL:*Status:*写完这道就去原*/#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;#defineendl'\n&

Floyd////CreatedbyLANSGANBSon2024/3/18.///**codetemplate:https://github.com/LANSGANBS/code-template*local:C:\Users\18019\CLionProjects\.cpp-code*URL:https://www.luogu.com.cn/problem/B3647*Status:AC*写完这道就去原*/#include<

感觉我太滞后了Day1T1Fish3我们可以做的操作是单点加\(D\)和后缀加\(1\)，考虑把这个操作放在差分数组上，则操作变成了：单点加\(1\)。\(i\)处加\(D\)，\(i+1\)处\(-D\)。需要最小化第二种操作的使用次数，发现只有对于所有差分数组中的负数是不得不用第二种操作的，而对于

设\(dist[x]\)表示源点到\(x\)的最短路的距离（图中无负环），若对图中任意一条边\((x,y,z)\)满足\(dist[y]≤dist[x]+z\)，那么\(dist\)就是最短路数组证：考虑任意一个点\(a\)，假设找出了一条源点到\(a\)的最短路径{\(x_0,x_1,...,x_n,a\)}，那么显然这条路径上\(x_0\)到任意一个点一定是最

拓扑序有这样一个问题：我们给定一张\(n\)个点\(m\)条边的有向无环图（DAG），请求出从\(1\)号结点出发，到达任意结点的最短路径，保证\(s\)可以到达任意结点，\(n,m\leq10^7\)。我们以下面这张图为例。如果我们想求\(1\rightarrow4\)的路径，我们不难发现，找到\(1\rightar

题目大意：给出一个01矩阵，求每个0移动(每次可以向有公共边的格子移动一步)到矩阵边界至少要经过多少个1。考虑建最短路模型，将矩阵中的每个位置拆分为入点和出点，矩阵外部设为一个点。枚举矩阵中的每个位置：如果这个位置在矩阵边界，矩阵外部向这个位置的入点连一条长度为0的边。

Dijkstra算法原理首先将所有点分为两类，确定和没确定最短路的点。首先我们可以知道，起点只能通过已经确定最短路的点去到其他点，所以我们可以不断的确定距离起点最近的点的路径长度，再用这个确定的点更新其他点到起点的最短路距离。此时找最近点为\(O(n)\)，更新邻接点为\(O(m)\)，

2001T4Car的旅行路线ybtluogu建图+最短路1.建图时细节较多已知三点求第四点的坐标勾股定理判断斜边2.最短路时多起点多终点2013D1T3货车运输ybtluogu最大生成树+倍增LCA答案的边一定在最大生成树上将原图建出最大生成树在树上使用倍增LCA提取路径2014D2T2寻

基本上用不到的算法，和高精度一样，不常用，用到了又无可代替常用于限制边数的最短路算法。使用范围可以处理任意边权的图，可以处理负环，可以判断负环。时间复杂度\(O(nm)\)。因为太慢了，在求最短路的时候基本用不到，但是它的优化版SPFA则大大优化了时间复杂度，算是最短路里最好用的算

题源狄克斯特拉【待完成】classSolution:defnetworkDelayTime(self,times:List[List[int]],n:int,k:int)->int:g=[[float('inf')]*nfor_inrange(n)]forx,y,timeintimes:g[x-1][y-1]=timedist

938-D题目大意给定一张\(n\)个顶点\(m\)条边的无向图，边带权，且每个点\(i\)有点权\(a[i]\)，记\(dist(i,j)\)为点\(i\)到点\(j\)所有的路径中经过的最小的边权和，请求出对于每个点\(i\)的：\[\min_j^n(dist(i,j)+a[j])\]Solution题目涉及最短路，启发我们使用\(dijkstra\)求解，但对每

最小生成树1486：【例题1】黑暗城堡求最短路径生成树的个数先求出根节点到各点的最短路径然后统计每个点的答案个数如果一个节点到1号节点的最短路=另一个和它有连边的节点到根节点的最短路+它们两个节点之间的直接距离这个点的个数++最后用乘法原理统计答案将每个点的