基础理论：
Floyd-Warshall算法的基本思想
初始化距离矩阵：
- 如果有一条边从顶点i到顶点j，距离为该边的权重。
- 如果i等于j（即同一个顶点），距离为0。
- 如果i不等于j且没有边相连，距离为正无穷大（表示不可达）。
动态规划更新距离：
- 使用一个三重循环，逐步考虑是否通过每一个顶点k可以缩短顶点i到顶点j的路径。
- 对于每个顶点对(i, j)，更新公式为：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
最终结果：
- 更新后的距离矩阵即为所有顶点对之间的最短路径。
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
void floydWarshall(vector<vector<int>>& dist) {
int n = dist.size();
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX) { // 防止加法溢出
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
int main() {
int n = 4;
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
// 边的定义 (u, v, w) 表示从 u 到 v 有一条权重为 w 的边
vector<vector<int>> edges = {
{0, 1, 5},
{0, 3, 10},
{1, 2, 3},
{2, 3, 1}
};
// 初始化距离矩阵
for (int i = 0; i < n; ++i) {
dist[i][i] = 0; // 自己到自己的距离为 0
}
for (auto& edge : edges) {
int u = edge[0];
int v = edge[1];
int w = edge[2];
dist[u][v] = w;
}
// 运行 Floyd-Warshall 算法
floydWarshall(dist);
// 输出所有顶点对之间的最短路径
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][j] == INT_MAX) {
cout << "INF ";
} else {
cout << dist[i][j] << " ";
}
}
cout << endl;
}
return 0;
}
Leetcode - 1334：阀值距离内邻居最少的城市：
题目：
有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。
注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
示例 1：
输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 输出：3 解释：城市分布图如上。 每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是： 城市 0 -> [城市 1, 城市 2] 城市 1 -> [城市 0, 城市 2, 城市 3] 城市 2 -> [城市 0, 城市 1, 城市 3] 城市 3 -> [城市 1, 城市 2] 城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。
笔记：
现将图存入邻接矩阵：dist，然后使用floyd得出各个点对的最小距离，最后遍历dist矩阵统计每个点可到节点的数量，然后就是从小到大遍历节点编号，如果count[i]小于等于res就更新res，并将i赋值给index。
class Solution {
public:
// floyd模板：
void floyd(vector<vector<int>>& dist){
int n = dist.size();
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(dist[i][k] < INT_MAX && dist[k][j] < INT_MAX){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
// 存图：
for(int i = 0; i < n; i++){
dist[i][i] = 0;
}
for(int i = 0; i < edges.size(); i++){
dist[edges[i][0]][edges[i][1]] = dist[edges[i][1]][edges[i][0]] = edges[i][2];
}
floyd(dist);
vector<int> count(n, 0);//存放各点能够到达的目的地个数
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(dist[i][j] != INT_MAX && dist[i][j] <= distanceThreshold){
count[i]++;
}
}
}
int res = INT_MAX;
int index;
for(int i = 0; i < n; i++){
if(count[i] <= res){
res = count[i];
index = i;
}
}
return index;
}
};Leetcode - 2976 ：转换字符串的最小成本I
题目：
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。
另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的成本。
你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。
返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。
注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。
示例 1：
输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20] 输出：28 解释：将字符串 "abcd" 转换为字符串 "acbe" ： - 更改下标 1 处的值 'b' 为 'c' ，成本为 5 。 - 更改下标 2 处的值 'c' 为 'e' ，成本为 1 。 - 更改下标 2 处的值 'e' 为 'b' ，成本为 2 。 - 更改下标 3 处的值 'd' 为 'e' ，成本为 20 。 产生的总成本是 5 + 1 + 2 + 20 = 28 。 可以证明这是可能的最小成本。
笔记：
这道题有些抽象，我们还是需要将字符转换成0-26的数字来进行处理，也就是将各位上的字母 - 'a'进行处理。
（1）建图：
因为是求source到target的最小代价，所以我们可以将其拆解为每一位变化的最小代价。这样一来我们就可以建立一个每一位字符的变换的邻接矩阵，dist[26][26],其中先全部初始化为LLONG_MAX(long long 型的最大值）
（2）求各位字母到达目标字母的最小代价：
这里我们采用floyd算法求出各个点对之间的最小代价，然后利用循环，将各位字母的最小代价叠加就是最后的转换最小代价。
class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
vector<vector<long long>> dist(26, vector<long long>(26, LLONG_MAX));
int n = source.size();
for(int i = 0; i < 26; i++){
dist[i][i] = 0;
}
for(int i = 0; i < original.size(); i++){
int a = original[i] - 'a';
int b = changed[i] - 'a';
dist[a][b] = min(dist[a][b], (long long)cost[i]);
}
for(int k = 0; k < 26; k++){
for(int i = 0; i < 26; i++){
for(int j = 0; j < 26; j++){
if(dist[i][k] < LLONG_MAX && dist[k][j] < LLONG_MAX){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
long long res = 0;
for(int i = 0; i < n; i++){
int x = source[i] - 'a';
int y = target[i] - 'a';
if(dist[x][y] == LLONG_MAX) return -1;
res += dist[x][y];
}
return res;
}
};Leetcode - 2959：关闭分部的可行集和数目：
题目：
一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。
公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。
两个分部之间的 距离 是通过道路长度之和的 最小值 。
给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的 无向 道路。
请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。
注意，关闭一个分部后，与之相连的所有道路不可通行。
注意，两个分部之间可能会有多条道路。
示例 1：
输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]] 输出：5 解释：可行的关闭分部方案有： - 关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。 - 关闭分部集合 [0,1] ，剩余分部为 [2] 。 - 关闭分部集合 [1,2] ，剩余分部为 [0] 。 - 关闭分部集合 [0,2] ，剩余分部为 [1] 。 - 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。 总共有 5 种可行的关闭方案。
笔记：
这里先对灵神的代码进行一波分析理解：
class Solution {
public:
int numberOfSets(int n, int maxDistance, vector<vector<int>> &roads) {
vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2)); // 防止加法溢出
for (int i = 0; i < n; i++) {
g[i][i] = 0;
}
for (auto &e: roads) {
int x = e[0], y = e[1], wt = e[2];
g[x][y] = min(g[x][y], wt);
g[y][x] = min(g[y][x], wt);
}
vector<vector<int>> f(n);
auto check = [&](int s) -> bool {
for (int i = 0; i < n; i++) {
if ((s >> i) & 1) { // 检查当前i节点是否在s中，若果在：
f[i] = g[i]; // 将节点i的邻接矩阵g[i]复制到f上
}
}
// Floyd
for (int k = 0; k < n; k++) {
if (((s >> k) & 1) == 0) continue;
for (int i = 0; i < n; i++) {
if (((s >> i) & 1) == 0) continue;
for (int j = 0; j < n; j++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
// 枚举当前的子集的每一位二进制数，如果该位数字不在子集就跳过：
for (int i = 0; i < n; i++) {
if (((s >> i) & 1) == 0) continue;
// 判断当前点所连接的所有边：1：连接点是否在当前子集 2：该链接边权值是否大于maxDistance
for (int j = 0; j < n; j++) {
if ((s >> j) & 1 && f[i][j] > maxDistance) {
return false;
}
}
}
return true;
};
int ans = 0;
for (int s = 0; s < (1 << n); s++) { // 枚举子集
ans += check(s);
}
return ans;
}
};
作者：灵茶山艾府
链接：https://leetcode.cn/problems/number-of-possible-sets-of-closing-branches/solutions/2560722/er-jin-zhi-mei-ju-floydgao-xiao-xie-fa-f-t7ou/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。以下是我的理解：
这道题的答题思路就是将图中所有节点的所有子集枚举出来判断是否符合题目中给定的的条件，如果当前自己符合题目所给定的条件，那我们就将ans加1。最后得到的ans即为可行的集合。
1）建图：
建立所给图的邻接矩阵，并将各节点到自身的距离初始化为0。
2）枚举所有子集：
将n各节点的每种子集枚举出来：
3）检查当前子集是否符合题目要求：
建立check函数，首先将当前自己对应的邻近矩阵传入到f，防止破坏原邻接矩阵，然后我们利用floyd算法得出每个节点对之间的最短距离，然后在进行对当前子集进行判断：枚举当前子集的每一位二进制数字，如果当前节点不在子集中就跳过，然后我们判断当前节点的所有边是否合法，如果不合法返回false，再循环完成后返回true，证明当前传入的子集是合法的一个选择。
class Solution {
public:
bool check(int s, int n, int maxDistance, const vector<vector<int>>& g){
// 当前字节的邻接矩阵
vector<vector<int>> f(n, vector<int>(n, INT_MAX / 2));
// 对当前子集的邻接矩阵进行赋值：
for(int i = 0; i < n; i++){
if((s >> i) & 1){
f[i] = g[i];
}
}
// floyd求每个子集中存在的节点对之间的最短距离
for(int k = 0; k < n; k++){
if(((s >> k) & 1) == 0) continue;
for(int i = 0; i < n; i++){
if(((s >> i) & 1) == 0) continue;
for(int j = 0; j < n; j++){
if(f[i][k] < INT_MAX && f[k][j] < INT_MAX){
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
}
for(int i = 0; i < n; i++){
if(((s >> i) & 1) == 0){
continue;
}
for(int j = 0; j < n; j++){
if(((s >> j) & 1) && f[i][j] > maxDistance){
return false;
}
}
}
return true;
}
int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
//1、建立邻接矩阵：
vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2));
for(int i = 0; i < n; i++){
g[i][i] = 0;
}
for(int i = 0; i < roads.size(); i++){
int x = roads[i][0];
int y = roads[i][1];
int w = roads[i][2];
g[x][y] = min(g[x][y], w);
g[y][x] = min(g[y][x], w);
}
int res = 0;
// 枚举n各节点的所有子集，判断是否合法：
for(int i = 0; i < (1 << n); i++){
res += check(i, n, maxDistance, g);
}
return res;
}
};