floyd

如题 可以理解为不断地消除中间节点k，把 i 和 j 经过中间节点的最短距离更新到 map[i][j]中， 相当于我们在i和j之间直接建立了一条可以用map[i][j]最短路径(把中间节点k消除了) 遍历n次就把所有的中间节点消除了，在任何两个节点 i，j 之间都建立了一条直连的最短路径map[i] ......

# 一、朴素 Floyd ```cpp for (int i = 1;i <= n; ++ i) { for (int j = 1;j <= n; ++ j) { for (int k = 1;k <= n; ++ k) { d[i][j] = min (d[i][j], d[i][k] + d[k ......

floyd 是一个全源最短路算法，时间复杂度 $O(n^3)$。 ~~时间好慢啊，但是超好写的好吗。~~ floyd 的本质其实就是动态规划。设 $dis_{i,j}$ 为 $i\to j$ 的最短路，转移方程便是寻找一个中间点 $k$，松弛 $i\to j$ 的路径，将其变为 $i\to k\to ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1142E "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1142/E "CF 传送门") 感觉很神奇啊，想了挺久的。 如果没有粉色边是容易 ......

Floyd算法（Floyd-Warshall算法）是一种用于求解图中所有顶点对之间最短路径的算法,该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法可以应用于许多方面，特别是在交通、物流和通信网络的优化中，譬如城市交通规划：Floyd算法可 ......

题目链接：[https://codeforces.com/problemset/problem/1196/F](https://codeforces.com/problemset/problem/1196/F) 题目大意： 给定一个包含 $n$ 个节点 $m$ 条边的无向图（$n,m \le 2 \ ......

比较神奇的题目。 首先考虑没有粉色边怎么做。我们可以按照连通块的思路来考虑，每次合并两个连通块。发现，只要我们合并两个连通块的根，最后一定会得到一棵外向树，而这样合并最后一定能够合并成一棵外向树，于是就可以在 $n - 1$ 次询问内得到答案。 考虑有粉色边怎么做。粉色边的问题其实就是导致有一些边不 ......

求最短路 for (int k = 1; k <= n; ++ k) { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } } } ......

注意事项: k 层循环不能内置 Floyd适用于求解全源最短路径问题，即对于给定的图G，求解任意两点之间的最短路径长度。 模板 #include<bits/stdc++.h> using namespace std; const int N=105; int dis[N][N]; void Floy ......

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，欢迎来到小彭的 LeetCode 周赛解题报告。 昨晚是 LeetCode 双周赛第 102 场，你参加了吗？这场比赛比较简单，拼的是板子手速，继上周掉大分后算是回了一口血 😁。 2618. 查询网 ......

leetcode141-环形链表 其算法应用龟兔赛跑的思想，使用一个slow和fast指针初始都指向链表第一个节点，slow每次向前走一步，fast向前走两步。如果链表无环，那么fast会先走到NULL节点。如果有环，那么当slow和fast都进入环的时候，由于fast比slow走的快，fast总会 ......

描述 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？ 输入 输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=1000 ......