过去我们一直在求单源最短路，今天让我们看一下多源最短路的求法。我们介绍一下它的核心思想：即不断在原有基础上添加新的中转点并求出此时的最优状态，是一种动态规划思想的体现。具体流程：我们先列出无中转点（也就是相邻的点）间的dis;然后枚举中转点k（有点类似区间dp),转移方程为f[i][j](从i到j)=min(f[i][j],f[i][k]+f[k][j]).正确性证明：当我们先枚举a为中转时，我们就可以求得任意两点之间经过与不经过a的最短距离。当我们先枚举b为中转时,我们就可以求得任意两点之间经过a与b的排列组合（不大准确，可以选一个，也可以都不选）（也就是ab与ba，a,b,0)同理，当我们

1.邻接表 staticclassEdge{intnext;intvalue;publicEdge(intnext,intvalue){this.next=next;this.value=value;}}staticHashMap>graph=newHashMap();publicstaticvoidaddEgde(intfrom,intto,intvalue){if(!graph.containsKey(from)){graph.put(from,newLinkedList());}if(!graph.containsKey(to)){graph.put(to,newLinkedList()

797.所有可能的路径题目:给你一个有n个节点的有向无环图（DAG），请你找出所有从节点0到节点n-1的路径并输出（不要求按特定顺序）graph[i]是一个从节点i可以访问的所有节点的列表（即从节点i到节点graph[i][j]存在一条有向边）。示例1：输入：graph=[[1,2],[3],[3],[]]输出：[[0,1,3],[0,2,3]]解释：有两条路径0->1->3和0->2->3示例2：输入：graph=[[4,3,1],[3,2,4],[3],[4],[]]输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]答案classSolutio

昨天复习的知识点。​先复习一下AOE网。AOE网，简单来说就是工程的带权有向图，其中：顶点：活动开始或者结束的事件边：活动边的权值：完成该活动所需的时间在AOE网中，想要完成一项活动，必须要先完成在该活动前面的所有活动，例如下图中，想要完成活动e，必须要先完成活动abcd，完成活动a和c所需时间为3+2=5，完成活动b和d所需时间为5+4=9，二者取大，因此任务e的最早开始时间为9。由此我们可以知道，整个工程从开始到结束所需要花费的时间是起始点到终止点的最大路径长度（因为这样才可以保证在终止点前的所有任务都完成了），这个有最大路径长度的路径就是关键路径，关键路径上的活动就叫做关键活动。​总的来

3.207.课程表你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1 。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i]=[ai,bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。例如，先修课程对 [0,1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。示例1：输入：numCourses=2,prerequisites=[[1,0]]输出：true解释：总共有2门课程。

作者推荐【数位dp】【动态规划】【状态压缩】【推荐】1012.至少有1位重复的数字涉及知识点深度优先搜索图论树LeetCode2646.最小化旅行的价格总和现有一棵无向、无根的树，树中有n个节点，按从0到n-1编号。给你一个整数n和一个长度为n-1的二维整数数组edges，其中edges[i]=[ai,bi]表示树中节点ai和bi之间存在一条边。每个节点都关联一个价格。给你一个整数数组price，其中price[i]是第i个节点的价格。给定路径的价格总和是该路径上所有节点的价格之和。另给你一个二维整数数组trips，其中trips[i]=[starti,endi]表示您从节点starti开始第

✨欢迎来到脑子不好的小菜鸟的文章✨      🎈创作不易，麻烦点点赞哦🎈     所属专栏：刷题_脑子不好的小菜鸟的博客-CSDN博客     我的主页：脑子不好的小菜鸟     文章特点：关键点和步骤讲解放在     代码相应位置拓扑排序/家谱树https://vjudge.net/contest/613618#problem/A//拓扑排序：找到入度为0的点，将其写入答案，再删去其箭头，再继续找入度为0的点，循环往复vectoredeg[101];intn,deg[101]={0};//入度voidinit()//建图{cin>>n;inti,val;for(i=1;i>val&&val!

本文涉及知识点图论割点双连通分类割点原理及封装好的割点类LeetCodeLCP54.夺回据点魔物了占领若干据点，这些据点被若干条道路相连接，roads[i]=[x,y]表示编号x、y的两个据点通过一条道路连接。现在勇者要将按照以下原则将这些据点逐一夺回：在开始的时候，勇者可以花费资源先夺回一些据点，初始夺回第j个据点所需消耗的资源数量为cost[j]接下来，勇者在不消耗资源情况下，每次可以夺回一个和「已夺回据点」相连接的魔物据点，并对其进行夺回注：为了防止魔物暴动，勇者在每一次夺回据点后（包括花费资源夺回据点后），需要保证剩余的所有魔物据点之间是相连通的（不经过「已夺回据点」）。请返回勇者夺回

终于是学完了，这个最短路我学了好几天，当然也学了别的算法啦，也是非常的累啊。话不多说下面看看最短路问题吧。最短路问题是有向图，要求的是图中一个点到起点的距离，其中我们要输入点和点之间的距离，来求最短路。下面分为几类题目：单源汇最短路-->一个起点1.边权为正数（dijkstra）dijkstra算法的原理其实是拿第一个点与相连接的点进行距离上的比较，让距离最近的点作为下一个比较的第一个点，由于是边权为正数，所以不用去考虑负数和负环路。但是为啥我要分为两种类型，不是因为优化就是比朴素好，因为他们的存储数据不同，要存储的方式也是不同的，所以方法也是不同的。方法：dis[1]=0,dis[i]=0x

一、图论    图论是数学的一个分支，它以图为研究对象。图论中的图是若干给定的点（顶点）以及连接两点的线（边）构成的图像，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。        图几乎可以用来表现所有类型的结构或系统，从交通网络到通信网络，从下棋游戏到最优流程，从任务分配到人际交互网络，图都有广阔的用武之地。表示出最基础的图：（这些与点的大小，边的粗细都无关，只表示点与点之间通过边的关系） 二、图的基础    1.顶点（vertex）     在图的应用中，每个顶点代表的含义均不相同，而是相互通过边相联系，因此将图中的每个顶点