文章目录一、Dijkstra算法1、1朴素版Dijkstra算法1、1、1 Dijkstra求最短路I1、1、2题解关键思路与与解答1、2堆优化版Dijkstra算法1、2、1 Dijkstra求最短路II1、2、2题解关键思路与答案二、Bellman-Ford算法2、1 Bellman-Ford算法求有边数限制的最短路2、1、1题目描述2、1、2题解关键思路与解答三、SPFA 算法3、1 spfa求最短路3、1、1题目描述3、1、2题解关键思路与解答四、Floyd算法4、1Floyd求最短路4、1、1题目描述4、1、2题解关键思路与解答五、总结🙋‍♂️ 作者：@Ggggggtm 🙋‍♂️

  文章目录一、Dijkstra算法1、1朴素版Dijkstra算法1、1、1 Dijkstra求最短路I1、1、2题解关键思路与与解答1、2堆优化版Dijkstra算法1、2、1 Dijkstra求最短路II1、2、2题解关键思路与答案二、Bellman-Ford算法2、1 Bellman-Ford算法求有边数限制的最短路2、1、1题目描述2、1、2题解关键思路与解答三、SPFA 算法3、1 spfa求最短路3、1、1题目描述3、1、2题解关键思路与解答四、Floyd算法4、1Floyd求最短路4、1、1题目描述4、1、2题解关键思路与解答五、总结🙋‍♂️ 作者：@Ggggggtm 🙋‍♂️

题意：​ 现在有一条河，河中有n个石头，你需要从河的一端到河的另一端。现在你有一次机会在任意位置放置一个石头，请问石头放在哪里可以使过河的最长路径最短。请输出放置的石头坐标。思路：​ n的规模是\(1e3\)，所以可以做到\(n^2\)的算法，我们把起点和终点也当做一块石头，基于贪心的思想，可以知道使最长路径最短的放法一定是在两个石子的中间点放。先预处理出起点到各个点的最短路和终点反跑到各个点的最短路，然后\(n^2\)枚举两个石头间距并将其缩短一半，更新答案。#includeusingnamespacestd;#definerep(i,a,n)for(inti=a;iPII;constint

题意：​ 现在有一条河，河中有n个石头，你需要从河的一端到河的另一端。现在你有一次机会在任意位置放置一个石头，请问石头放在哪里可以使过河的最长路径最短。请输出放置的石头坐标。思路：​ n的规模是\(1e3\)，所以可以做到\(n^2\)的算法，我们把起点和终点也当做一块石头，基于贪心的思想，可以知道使最长路径最短的放法一定是在两个石子的中间点放。先预处理出起点到各个点的最短路和终点反跑到各个点的最短路，然后\(n^2\)枚举两个石头间距并将其缩短一半，更新答案。#includeusingnamespacestd;#definerep(i,a,n)for(inti=a;iPII;constint