路径的问题分为使用BFS和使用迪斯科特拉算法这两种算法求解的范围是有区别的

BFS迪斯科特拉算法适合求解边的权值不一样的图其中该算法有两种实现方式分别适用于两种情况的图

稠密图使用朴素的Dijkstra算法其中稠密图的定义是边的数量级与

o(n^2)

o(n2),其中n是图的节点的数量稀疏图使用堆优化的Dijkstra算法算法的时间复杂度是

o(mlogm)

o(mlogm)其中m是边的数量如果输入的稠密图那么使用堆优化的Dijkstra算法的时间复杂度是

o(n^2logn)

times:edge[x-1].append((y-1,z))dis

[float(inf)]*n

new_disheapq.heappush(h,(new_dis,y))mx

max(dis)return

思路分析由于边的数量远远大于节点的数量所以我们还是考虑使用稠密图下的朴素的Dijkstra算法最后返回不是无穷的最大的路径即可

class

times:edge[x-1].append((y-1,z))dis

[float(inf)]*n

new_disheapq.heappush(h,(new_dis,y))mx

max(dis)return

所以写了一个动态规划进行求解实际上这个思路是错误的,不过要是只能向下或者向右运动的话动态规划也是一种很好的做法

import

开始的时候从(0,0)出发移动到相邻的房间其实也只是向下或向右运动#

感觉可以用动态规划dp[i][j]表示到达i,j所需的最少的时间#

递推公式#

min(max(dp[i-1][j],moveTime[i][j])1,max(dp[i][j-1],moveTime[i][j])1)n

len(moveTime)m

min(max(dp[i][j1],moveTime[i][j])1,max(dp[i1][j],moveTime[i][j])1)for

dp:print(i

正确的思路应该是使用Dijkstra算法不过开始的时候我有点纠结这个edge也就是边的矩阵如何转化为邻接矩阵或者邻接表后面一想还是我的固定思维阻碍了我邻接矩阵和邻接表只是一个工具帮助我们找到当前的节点的邻居但是在现在的图中你通过坐标的加减不就可以得到对应的邻居嘛

展示使用朴素Dijkstra算法做法

dis[i][j]表示(0,0)到(i,j)的最短的时间n,m

len(moveTime),len(moveTime[0])dis

[[float(inf)]*m

(x1,y),(x-1,y),(x,y1),(x,y-1):if

and

min(max(dis[x][y],moveTime[i][j])

1,dis[i][j])

dis[i][j]表示(0,0)到(i,j)的最短的时间n,m

len(moveTime),len(moveTime[0])dis

[[float(inf)]*m

(x1,y),(x-1,y),(x,y1),(x,y-1):if

and

new_disheapq.heappush(h,(dis[i][j],i,j))