2024.3.26 题目来源我的题解方法一 Dijkstra算法求最短路径方法二 Floyd算法求最短路径 题目来源 力扣每日一题；题序：2642 我的题解 方法一 Dijkstra算法求最短路径 图使用邻接表存储，添加边只需要更新邻接表就行。 求两个节点的路径最小代价使用dijkstra算法来实现 时间复杂度： Graph 类初始化时，时间复杂度为 O(m

解题思路 状态定义， d p [ u ] [ v ] [ k ] dp[u][v][k] dp[u][v][k]代表从城市 u u u到达城市 v v v，最多经过 k k k个中转站得到的最小的距离。本题中，源城市确定，显然这里上面定义状态的第一维 u u u就不需要了，所以我们的状态 d p [ v ] [ k ] dp[v][k] dp[v][k]代表从城市 s r c src src到达