Leetcode解题或者面试刷题有时会需要储备一些已有的算法思想，而不全是凭借临场发挥。
因为有些问题如果不是记住了对应解决思路，在短时间内是很难或者说基本不太可能凭经验试探出来的。比如最短路径的问题，学习过《数据结构与算法》的朋友可能会记得dijkstra算法和floyd算法。而这两种算法是目前解决这类问题时最高效的，也是事实上公认的标准算法。这里就借助 Leetcode Q1334问题简要谈一谈。1. 题目 Q1334 查找阈值距离内邻居最少的城市
有个城市，编号从到。给定数组边，其中 edge[i] = [，，] 代表城市 和 之间的双向和加权边，并给出整数 distanceThreshold。返回通过某些路径可到达且距离最大为distanceThreshold的城市数量最少的城市，如果有多个这样的城市，则返回编号最大的城市。请注意，连接城市i和j的路径的距离等于沿该路径的边权重之和。
约束条件：
- (a) 2 <= n <= 100
- (b) 1 <= edges.length <= n * (n - 1) / 2
- (c) edges[i].length == 3
- (d) 0 <= < n
- (e) 1 <= , distanceThreshold
- (f) 所有点对 (fromi, toi) 是不重复的.
示例1
示例1网络图
<code>Input: n =4
, edges =[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
, distanceThreshold =4
Output:3
/<code>
解释： 上方图片描述了一个Graph。对任何一个城市满足distanceThreshold = 4要求的城市如下：
<code>City
0
->
[City
1
,
City
2
]
City
1
->
[City
0
,
City
2
,
City
3
]
City
2
->
[City
0
,
City
1
,
City
3
]
City
3
->
[City
1
,
City
2
]
/<code>
城市0和城市3都有两个邻居满足要求，但是我们必须返回城市3，因为它在符合基本要求的情况下，编号最大。
示例2
示例2网络图
<code>Input: n =5
, edges =[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]]
, distanceThreshold =2
Output:0
/<code>
解释： 上图描述了输入的Graph。对任何一个城市满足distanceThreshold = 2要求的城市如下：
<code>City
0
->
[City
1
]
City
1
->
[City
0
,
City
4
]
City
2
->
[City
3
,
City
4
]
City
3
->
[City
2
,
City
4
]
City
4
->
[City
1
,
City
2
,
City
3
]
/<code>
城市0 有一个邻居，并满足基本要求。
2. 解题思路
乍一看这题目还挺吓人，描述长、要求多，还涉及到Graph。但真正的要求其实就只有两个：
<code>(1) 找到要求距离内的邻居； (2) 返回邻居最少的城市编号。/<code>
事实上，难点就在第一个要求，即指定距离内的邻居。这个要求的表述与“最短路径”存在一些差异，导致很多朋友难以联想到使用“最短路径”算法来解决。如果将这个要求翻译成以下表述就清晰多了：
<code>找到与邻居最短距离在要求数值之内的城市/<code>
对于那些求解指定起点到指定重点之间距离的问题，可以使用dijkstra算法；但对于这种求解一个点集的任意两点之间的最短距离，应当使用floyd算法。
3. Floyd算法基本流程
使用伪代码表述的Floyd算法如下：
<code>Input
:edges, n x 3, [start, end, distance]
Initialize
:dist, n x n, MAX_NUM
------------------------------
Step1
:dist = fill_edges(edges)
Step2
:for i in range(0, n):
for
j in range(0, n):
for
k in range(0, n):
if
j == k :
continue
d
=dist[j][i] + dist[i][k];
if
dist[j][k] > d:
=d;
-----------------------------
Output
:dist
/<code>
最终得到dist数组中的第i行第j列就存储着城市i到城市j的最短距离。如果还想得到最短距离的具体路径，那么在以上算法流程的基础上，还需要记录更多的信息，比如，生成当前最短距离的父节点。在解决当前这个问题时倒是不需要那么复杂。从算法描述来看，Floyd算法的时间复杂度是。虽然比我们日常处理其他问题的复杂度高，但这已经是目前最快的算法了。
4. C++解决方案
以下给出具体的C++解决方案。
从Leetcode上的评测来看，当前解决方案已经超过了98%的提交，应该来说算是一个不错的解决方案。试想，如果我们没有记住Floyd算法，那么在临场发挥的时候能够想的出来这其中复杂的逻辑吗？当然不排除有个别的天才，但是对于面试而言，还是谨慎稳重一点比较靠谱。那么积累一些业内公认的标准算法还是很必要的。
----------------------
题外：
频道资源，可以私信关键字获取。
Python编程问题咨询，请发送关键字【咨询】
获取leetcode源代码，请发送关键字【leetcode】
获取书籍，请发送关键字【书籍】
關鍵字: distanceThreshold 路径 短距离
