你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。
输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。
给你一个整数 n 和二维整数数组 roads ，
其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。
你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 7 取余 后返回。
示例 1：输入：n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
输出：4
解释：从路口 0 出发到路口 6 花费的最少时间是 7 分钟。
四条花费 7 分钟的路径分别为：
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
示例 2：输入：n = 2, roads = [[1,0,10]] 输出：1
解释：只有一条从路口 0 到路口 1 的路，花费 10 分钟。
提示：1 <= n <= 200
n - 1 <= roads.length <= n * (n - 1) / 2
roads[i].length == 3
0 <= ui, vi <= n - 1
1 <= timei <= 109
ui != vi
任意两个路口之间至多有一条路。
从任意路口出发，你能够到达其他任意路口。
1、Dijkstra+动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)
var mod = 1000000007
func countPaths(n int, roads [][]int) int {
maxValue := int(1e11) // math.MaxInt32=2147483647 才10位<200*1e9，可以使用11位或者更大
arr := make([][]int, n) // 邻接矩阵：i=>j的最短距离
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = maxValue
}
}
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
arr[a][b] = c
arr[b][a] = c
}
dis := make([]int, n)
for i := 0; i < n; i++ {
dis[i] = maxValue
}
dis[0] = 0
visited := make([]bool, n)
for i := 0; i < n; i++ {
target := -1 // 寻找未访问的距离起点最近点
for j := 0; j < n; j++ {
if visited[j] == false && (target == -1 || dis[j] < dis[target]) {
target = j
}
}
visited[target] = true
for j := 0; j < n; j++ { // 更新距离
dis[j] = min(dis[j], dis[target]+arr[target][j])
}
}
// 计算某条边是否在边上
edge := make([]int, n) // 入度
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if dis[i]+arr[i][j] == dis[j] {
edge[j]++ // 入度+1
}
}
}
dp := make([]int, n) // dp[i] 表示0=>i的最短路个数
dp[0] = 1
queue := make([]int, 0)
queue = append(queue, 0)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for j := 0; j < n; j++ {
if dis[node]+arr[node][j] == dis[j] {
dp[j] = (dp[j] + dp[node]) % mod
edge[j]-- // 入度-1
if edge[j] == 0 { // 入队
queue = append(queue, j)
}
}
}
}
return dp[n-1] % mod
}
func min(a, b int) int {
if a > b {
return b
}
return a
}2、Floyd+递归；时间复杂度O(n^3)，空间复杂度O(n^2)
var mod = 1000000007
var dp []int
func countPaths(n int, roads [][]int) int {
maxValue := int(1e12) // math.MaxInt32=2147483647 才10位<200*1e9，可以使用11位或者更大，这里使用11不行
arr := make([][]int, n) // 邻接矩阵：i=>j的最短距离
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = maxValue
}
arr[i][i] = 0
}
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
arr[a][b] = c
arr[b][a] = c
}
arr = Floyd(arr)
path := make([][]int, n)
dp = make([]int, n)
for i := 0; i < n; i++ {
path[i] = make([]int, 0)
dp[i] = -1
}
// 构建图，都是从下标0开始
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
if arr[0][b]-arr[0][a] == c {
path[a] = append(path[a], b)
} else if arr[0][a]-arr[0][b] == c {
path[b] = append(path[b], a)
}
}
return dfs(path, 0)
}
func dfs(path [][]int, index int) int {
if index == len(path)-1 {
return 1
}
if dp[index] != -1 {
return dp[index]
}
dp[index] = 0
for i := 0; i < len(path[index]); i++ {
next := path[index][i]
dp[index] = (dp[index] + dfs(path, next)) % mod
}
return dp[index]
}
func Floyd(arr [][]int) [][]int {
n := len(arr)
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if arr[i][k]+arr[k][j] < arr[i][j] {
arr[i][j] = arr[i][k] + arr[k][j]
}
}
}
}
return arr
}3、Floyd+动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)
var mod = 1000000007
func countPaths(n int, roads [][]int) int {
if n <= 2 {
return 1
}
maxValue := int(1e12) // math.MaxInt32=2147483647 才10位<200*1e9，可以使用11位或者更大，这里使用11不行
arr := make([][]int, n) // 邻接矩阵：i=>j的最短距离
dp := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
dp[i] = make([]int, n)
for j := 0; j < n; j++ {
arr[i][j] = maxValue
}
arr[i][i] = 0
}
for i := 0; i < len(roads); i++ {
a, b, c := roads[i][0], roads[i][1], roads[i][2]
arr[a][b] = c
arr[b][a] = c
dp[a][b] = 1
dp[b][a] = 1
}
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
if arr[i][k] == maxValue { // 不联通
continue
}
for j := 0; j < n; j++ {
// 不联通/距离大于当前值
if arr[j][k] == maxValue || arr[i][k]+arr[k][j] > arr[i][j] {
continue
}
if arr[i][k]+arr[k][j] < arr[i][j] {
dp[i][j] = (dp[i][k] * dp[k][j]) % mod
arr[i][j] = arr[i][k] + arr[k][j]
} else if arr[i][k]+arr[k][j] == arr[i][j] {
dp[i][j] = (dp[i][j] + dp[i][k]*dp[k][j]) % mod
}
}
}
}
return dp[0][n-1]
}4、Dijkstra+堆+动态规划；时间复杂度O(nlog(n))，空间复杂度O(n^2)
var mod = 1000000007
func countPaths(n int, roads [][]int) int {
mathValue := int(1e12)
arr := make([][][2]int, n)
for i := 0; i < len(roads); i++ { // 邻接表
a, b, c := roads[i][0], roads[i][1], roads[i][2]
arr[a] = append(arr[a], [2]int{b, c})
arr[b] = append(arr[b], [2]int{a, c})
}
dp := make([]int, n)
dis := make([]int, n) // 0到其他点的距离
for i := 0; i < n; i++ {
dis[i] = mathValue
}
dis[0] = 0
dp[0] = 1
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
heap.Push(&intHeap, [2]int{0, 0})
for intHeap.Len() > 0 {
node := heap.Pop(&intHeap).([2]int)
a, d := node[0], node[1]
if dis[a] < d {
continue
}
for i := 0; i < len(arr[a]); i++ {
b, c := arr[a][i][0], arr[a][i][1]
if dis[a]+c < dis[b] {
dis[b] = dis[a] + c
dp[b] = dp[a]
heap.Push(&intHeap, [2]int{b, dis[b]})
} else if dis[a]+c == dis[b] {
dp[b] = (dp[b] + dp[a]) % mod
}
}
}
return dp[n-1] % mod
}
type IntHeap [][2]int
func (h IntHeap) Len() int {
return len(h)
}
// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
return h[i][1] < h[j][1]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.([2]int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}Medium题目，最短路问题+动态规划，注意最大值的范围
页面更新：2024-05-18
本站资料均由网友自行发布提供，仅用于学习交流。如有版权问题，请与我联系，QQ：4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号
