Floyd-Warshall解题模板助你快速AC

Floyd-Warshall是一种求解任意两点之间最短路径的算法。LeetCode用过很多题。掌握这个解题模板，可以帮助你快速AC。题目地址（1334.阈值距离内邻居最少的城市）https://leetcode-cn.com/probl...题目描述中有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内的相邻城市分别为：City0->[City1,City2]City1->[City0,City2,City3]City2->[City0,City1,city3]city3->[city1,city2]城市0和3在阈值距离4内都有2个相邻城市，但我们必须返回城市3，因为它的数量最多。示例2：输入：n=5，edges=[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]],distanceThreshold=2输出：0解释：城市分布图如上。每个城市在阈值距离distanceThreshold=2内的相邻城市为：City0->[City1]City1->[City0,City4]City2->[City3,City4]City3->[City2,City4]City4->[City1,City2,City3]City0在阈值距离4内只有1个相邻城市。提示：2<=n<=1001<=edges.length<=n*(n-1)/2edges[i].length==30<=fromiint:#构建dist矩阵dist=[[float('inf')]*nfor_inrange(n)]fori,j,winedges:dist[i][j]=wdist[j][i]=wforiinrange(n):dist[i][i]=0forkinrange(n):foriinrange(n):forjinrange(n):dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])#过滤器res=0minCnt=float('inf')foriinrange(n):cnt=0fordindist[i]:ifd<=distanceThreshold:cnt+=1ifcnt<=minCnt:minCnt=cntres=ireturnres关键点分析Floyd-Warshall算法可以使用本文给出的Floyd-Warshalll算法作为解题模板