046.Dijkstra 算法、分层图最短路

前置知识：讲解 025、027 堆结构、位图、建图、Prim 算法利用反向索引堆做的优化、宽度优先遍历及其扩展

Dijkstra 算法 §

戴克斯特拉算法

解决的问题：给定一个源点，求解从源点到每个点的最短路径长度。单源最短路径算法。

适用范围：

1. 有向图（无向图可以看成两个方向的有向图，也可以解）
2. 边的权值没有负值（有负值使用 Bellman-Ford 算法 来解）

彻底暴力的 Dijkstra 算法 §

不讲，时间复杂度太差（$O(n^2)$），无意义

普通堆实现的 Dijkstra 算法 §

最普遍、最常用

思路和 01bfs 差不多，将双端队列变成小根堆

算法过程：

1. distance[i] 表示从源点到 i 点的最短距离，visited[i] 表示 i 节点是否从小根堆弹出过
2. 准备好小根堆，小根堆存放记录：(x 点, 源点到 x 的距离)，小根堆根据距离组织
   • 一个点可能在堆中有多条记录
   • 但是最先弹出来的就是最短的距离，之后的记录就不做处理，跳过了
3. 令 distance[源点]=0，(源点, 0) 进入小根堆
4. 从小根堆弹出 (u 点, 源点到 u 的距离)
   • 如果 visited[u] == true，不做任何处理，重复步骤 4
   • 如果 visited[u] == false，令 visited[u] = true，u 就算弹出过了。然后考察 u 的每一条边，假设某边去往 v，边权为 w
     • 如果 visited[v] == false 并且 distance[u] + w < distance[v]，令 distance[v] = distance[u] + w，把 (v, distance[u] + w) 加入小根堆
     • 处理完 u 的每一条边之后，重复步骤 4
5. 小根堆为空过程结束，distance 表记录了源点到每个节点的最短距离。

算法核心过程：

• 节点弹出过就忽略
• 节点没弹出过，让其它没弹出节点距离变小的记录加入堆

普通堆实现的 Dijkstra 算法，时间复杂度 $O(m\ast lo{g}^m)$，$m$ 为边数，堆数据量和边有关

反向索引堆实现的 Dijkstra 算法 §

最快速、最极致（点数据量小、边数据量大的情况下，比普通堆实现的 Dijkstra 算法快很多）

和 Prim 算法的优化 差不多

算法过程：

1. 准备好反向索引堆，根据源点到当前点的距离组织小根堆，可以做到如下操作
   • 新增记录 (x, 源点到 x 的距离)
   • 当源点到 x 的距离更新时，可以进行堆的调整
   • x 点一旦弹出，以后忽略 x
   • 弹出堆顶的记录 (u, 源点到 u 的距离)
2. 把 (源点, 0) 加入反向索引堆，过程开始
3. 反向索引堆弹出 (u, 源点到 u 的距离)，考察 u 的每一条边，假设某边去往 v，边权为 w
   • 如果 v 没有进入过反向索引堆里，新增记录 (v, 源点到 u 的距离 + w)
   • 如果 v 曾经从反向索引堆弹出过，忽略
   • 如果 v 在反向索引堆里，看看源点到 v 的距离能不能变得更小，如果能，调整堆；不能，忽略
   • 处理完 u 的每一条边，重复步骤 3
4. 反向索引堆为空过程结束。反向索引堆里记录了源点到每个节点的最短距离。

核心在于掌握反向索引堆

反向索引堆实现的 Dijkstra 算法，时间复杂度 $O(m\ast lo{g}^n$)，$n$ 为节点数，$m$ 为边数，堆数据量和点有关

对应本节题目1、题目2、题目3

题目1.Dijkstra 模板 §

题目描述 §

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

提示：

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• 所有 (ui, vi) 对都 互不相同（即，不含重复边）

测试链接 §

• 力扣：743.网络延迟时间
• 洛谷：P4779【模板】单源最短路径（标准版）

邻接表 + 普通堆的实现 §

const (
	MAX_INT = math.MaxInt
)
 
func networkDelayTime(times [][]int, n int, k int) int {
	graph := make([][][2]int, n+1)
	for i := range graph {
		graph[i] = [][2]int{}
	}
	for _, edge := range times {
		from := edge[0]
		to := edge[1]
		weight := edge[2]
		graph[from] = append(graph[from], [2]int{to, weight})
	}
	visited := make([]bool, n+1)
	distance := make([]int, n+1)
	for i := range distance {
		distance[i] = MAX_INT
	}
	minHeap := MinHeap{}
	heap.Push(&minHeap, [2]int{k, 0})
	distance[k] = 0
	for minHeap.Len() > 0 {
		cur := heap.Pop(&minHeap).([2]int)[0]
		if visited[cur] {
			continue
		}
		visited[cur] = true
		for _, edge := range graph[cur] {
			to := edge[0]
			weight := edge[1]
			if !visited[to] && distance[cur]+weight < distance[to] {
				distance[to] = distance[cur] + weight
				heap.Push(&minHeap, [2]int{to, distance[cur] + weight})
			}
		}
	}
	minn := 0
	for _, v := range distance[1:] {
		if v == MAX_INT {
			return -1
		}
		if v > minn {
			minn = v
		}
	}
	return minn
}
 
// [当前点, 当前点到原点的距离]
type MinHeap [][2]int
 
func (h MinHeap) Len() int {
	return len(h)
}
 
func (h MinHeap) Less(i, j int) bool {
	return h[i][1] < h[j][1]
}
 
func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
 
func (h *MinHeap) Push(v any) {
	*h = append(*h, v.([2]int))
}
 
func (h *MinHeap) Pop() any {
	n := len(*h)
	res := (*h)[n-1]
	*h = (*h)[:n-1]
	return res
}

链式前向星 + 反向索引堆实现 §

const (
	MAXN    = 101
	MAXM    = 6001
	MAX_INT = math.MaxInt
)
 
var (
	head     = [MAXN]int{}
	next     = [MAXM]int{}
	to       = [MAXM]int{}
	weight   = [MAXM]int{}
	cnt      = 1
	minHeap  = MinHeap{}
	heapSize = 0
	// 某点在堆中的位置
	// -2: 已经从堆中弹出
	// -1: 未入过堆
	// >0: 堆的下标
	// 可以完全覆盖 visited 的作用
	where    = [MAXN]int{}
	distance = [MAXN]int{}
)
 
func build(n int) {
	for i := 1; i <= n; i++ {
		head[i] = 0
		where[i] = -1
		distance[i] = MAX_INT
	}
	cnt = 1
	heapSize = 0
}
 
func addEdge(f, t, w int) {
	next[cnt] = head[f]
	to[cnt] = t
	weight[cnt] = w
	head[f] = cnt
	cnt++
}
 
func networkDelayTime(times [][]int, n int, k int) int {
	build(n)
	for _, edge := range times {
		addEdge(edge[0], edge[1], edge[2])
	}
	addOrUpdateOrIgnore(k, 0)
	for heapSize > 0 {
		cur := heap.Pop(&minHeap).(int)
		for i := head[cur]; i > 0; i = next[i] {
			addOrUpdateOrIgnore(to[i], distance[cur]+weight[i])
		}
	}
	minn := 0
	for i := 1; i <= n; i++ {
		if distance[i] == MAX_INT {
			return -1
		}
		if distance[i] > minn {
			minn = distance[i]
		}
	}
	return minn
}
 
func addOrUpdateOrIgnore(v, w int) {
	if where[v] == -2 {
		// 跳过，什么也不做
	} else if where[v] == -1 {
		distance[v] = w
		heap.Push(&minHeap, v)
	} else {
		if w < distance[v] {
			distance[v] = w
			heap.Fix(&minHeap, where[v])
		}
	}
}
 
// 只存一个当前点，当前点到原点的距离在 distance 可以取到
type MinHeap [MAXN]int
 
func (*MinHeap) Len() int {
	return heapSize
}
 
func (h *MinHeap) Less(i, j int) bool {
	return distance[h[i]] < distance[h[j]]
}
 
func (h *MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
	where[h[i]] = i
	where[h[j]] = j
}
 
func (h *MinHeap) Push(v any) {
	val := v.(int)
	h[heapSize] = val
	where[val] = heapSize
	heapSize++
}
 
func (h *MinHeap) Pop() any {
	heapSize--
	res := h[heapSize]
	where[res] = -2
	return res
}

题目2.最小体力消耗路径 §

题目描述 §

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值。

提示：

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 10^6

测试链接 §

1631.最小体力消耗路径

答案 §

const (
	MAX_INT = math.MaxInt
)
 
var (
	move = [5]int{-1, 0, 1, 0, -1}
)
 
func minimumEffortPath(heights [][]int) int {
	n := len(heights)
	m := len(heights[0])
	distance := make([][]int, n)
	visited := make([][]bool, n)
	for i := 0; i < n; i++ {
		distance[i] = make([]int, m)
		visited[i] = make([]bool, m)
		for j := 0; j < m; j++ {
			distance[i][j] = MAX_INT
		}
	}
	minHeap := MinHeap{}
	distance[0][0] = 0
	heap.Push(&minHeap, [3]int{0, 0, 0})
	for len(minHeap) > 0 {
		cur := heap.Pop(&minHeap).([3]int)
		x := cur[0]
		y := cur[1]
		w := cur[2]
		if visited[x][y] {
			continue
		}
		if x == n-1 && y == m-1 {
			// 常见剪枝：发现终点直接返回，不用等都结束
			return w
		}
		visited[x][y] = true
		for i := 0; i < 4; i++ {
			nx := x + move[i]
			ny := y + move[i+1]
			if nx < 0 || nx == n || ny < 0 || ny == m || visited[nx][ny] {
				continue
			}
			nw := max(w, abs(heights[x][y]-heights[nx][ny]))
			if nw < distance[nx][ny] {
				distance[nx][ny] = nw
				heap.Push(&minHeap, [3]int{nx, ny, nw})
			}
		}
	}
	return -1
}
 
func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}
 
// [x, y, 当前点到原点的距离]
type MinHeap [][3]int
 
func (h MinHeap) Len() int {
	return len(h)
}
 
func (h MinHeap) Less(i, j int) bool {
	return h[i][2] < h[j][2]
}
 
func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
 
func (h *MinHeap) Push(v any) {
	*h = append(*h, v.([3]int))
}
 
func (h *MinHeap) Pop() any {
	n := len(*h)
	res := (*h)[n-1]
	*h = (*h)[:n-1]
	return res
}

复杂度 §

• 时间复杂度：$O(n\ast m\ast lo{g}^{n\ast m})$
• 空间复杂度：$O(n\ast m)$

题目3.水位上升的泳池中游泳 §

题目描述 §

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间。

提示:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] < n^2
• grid[i][j] 中每个值 均无重复

测试链接 §

778.水位上升的泳池中游泳

答案 §

const (
	MAX_INT = math.MaxInt
)
 
var (
	move = [5]int{-1, 0, 1, 0, -1}
)
 
func swimInWater(grid [][]int) int {
	n := len(grid)
	distance := make([][]int, n)
	visited := make([][]bool, n)
	for i := 0; i < n; i++ {
		distance[i] = make([]int, n)
		visited[i] = make([]bool, n)
		for j := 0; j < n; j++ {
			distance[i][j] = MAX_INT
		}
	}
	minHeap := MinHeap{}
	distance[0][0] = grid[0][0]
	heap.Push(&minHeap, [3]int{0, 0, grid[0][0]})
	for len(minHeap) > 0 {
		cur := heap.Pop(&minHeap).([3]int)
		x := cur[0]
		y := cur[1]
		w := cur[2]
		if visited[x][y] {
			continue
		}
		if x == n-1 && y == n-1 {
			return w
		}
		visited[x][y] = true
		for i := 0; i < 4; i++ {
			nx := x + move[i]
			ny := y + move[i+1]
			if nx < 0 || nx == n || ny < 0 || ny == n || visited[nx][ny] {
				continue
			}
			nw := max(w, grid[nx][ny])
			if nw < distance[nx][ny] {
				distance[nx][ny] = nw
				heap.Push(&minHeap, [3]int{nx, ny, nw})
			}
		}
	}
	return -1
}
 
// [x, y, 当前点到原点的距离]
type MinHeap [][3]int
 
func (h MinHeap) Len() int {
	return len(h)
}
 
func (h MinHeap) Less(i, j int) bool {
	return h[i][2] < h[j][2]
}
 
func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
 
func (h *MinHeap) Push(v any) {
	*h = append(*h, v.([3]int))
}
 
func (h *MinHeap) Pop() any {
	n := len(*h)
	res := (*h)[n-1]
	*h = (*h)[:n-1]
	return res
}

复杂度 §

• 时间复杂度：$O(n\ast m\ast lo{g}^{n\ast m})$
• 空间复杂度：$O(n\ast m)$

分层图最短路 §

分层图最短路，又叫扩点最短路

有经典 bfs 来解的分层图最短路问题，也有用 Dijkstra 算法来解的分层图最短路问题，算是 Dijkstra 的扩展

不把实际位置看做图上的点，而是把实际位置及其状态的组合看做是图上的点（一个实际的点可能扩出来多个点），然后搜索

bfs 或者 Dijkstra 的过程不变，只是扩了点（分层）而已

原理简单，核心在于如何扩点、如何到达、如何算距离，每个题可能都不一样

题目1.获取所有钥匙的最短路径 §

题目描述 §

给定一个二维网格 grid ，其中：

• ’.’ 代表一个空房间
• ’#’ 代表一堵墙
• ’@’ 是起点
• 小写字母代表钥匙
• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1。

示例 1：

输入：grid = ["@.a..","###.#","b.A.B"]

输出：8

解释：目标是获得所有钥匙，而不是打开所有锁。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 30
• grid[i][j] 只含有 '.', '#', '@', 'a'-``'f``' 以及 'A'-'F'
• 钥匙的数目范围是 [1, 6]
• 每个钥匙都对应一个 不同 的字母
• 每个钥匙正好打开一个对应的锁

测试链接 §

864.获取所有钥匙的最短路径

思路 §

经典 bfs 的分层图最短路，点还要加一个 位图 信息来表示当前拿到的钥匙

答案 §

var (
	move = [5]int{-1, 0, 1, 0, -1}
)
 
func shortestPathAllKeys(grid []string) int {
	n := len(grid)
	m := len(grid[0])
	// [x, y, 拥有钥匙的位图]
	queue := [][3]int{}
	// 所有钥匙的位图
	key := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == '@' {
				queue = append(queue, [3]int{i, j, 0})
			} else if grid[i][j] >= 'a' && grid[i][j] <= 'f' {
				key |= 1 << (grid[i][j] - 'a')
			}
		}
	}
	visited := make([][][]bool, n)
	for i := range visited {
		visited[i] = make([][]bool, m)
		for j := range visited[i] {
			visited[i][j] = make([]bool, key)
		}
	}
	level := 1
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			x := queue[i][0]
			y := queue[i][1]
			s := queue[i][2]
			for j := 0; j < 4; j++ {
				nx := x + move[j]
				ny := y + move[j+1]
				ns := s
				if nx < 0 || nx == n || ny < 0 || ny == m {
					// 越界
					continue
				}
				char := grid[nx][ny]
				if char == '#' {
					// 障碍
					continue
				}
				if char >= 'A' && char <= 'F' && ns&(1<<(char-'A')) == 0 {
					// 是锁，但没有对应的钥匙
					continue
				}
				if char >= 'a' && char <= 'f' {
					// 是某一把钥匙
					ns |= 1 << (char - 'a')
				}
				if ns == key {
					// 所有钥匙都收集完了
					return level
				}
				if !visited[nx][ny][ns] {
					visited[nx][ny][ns] = true
					queue = append(queue, [3]int{nx, ny, ns})
				}
			}
		}
		level++
		queue = queue[size:]
	}
	return -1
}

题目2.电动车游城市 §

题目描述 §

小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间。小明想选择电动车作为代步工具。

地图上共有 N 个景点，景点编号为 0 ~ N-1。他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，表示城市 A、B 间存在双向通路。

初始状态，电动车电量为 0。每个城市都设有充电桩，charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end。

提示：

• 1 <= paths.length <= 200
• paths[i].length == 3
• 2 <= charge.length == n <= 100
• 0 <= path[i][0],path[i][1],start,end < n
• 1 <= cnt <= 100
• 1 <= path[i][2] <= cnt
• 1 <= charge[i] <= 100
• 题目保证所有城市相互可以到达

测试链接 §

LCP 35.电动车游城市

思路 §

Dijkstra 算法的分层图最短路，扩出来的点：到达某个城市和到达时的电量

答案 §

const (
	MAX_INT = math.MaxInt
)
 
func electricCarPlan(paths [][]int, cnt int, start int, end int, charge []int) int {
	n := len(charge)
	graph := make([][][2]int, n)
	for i := range graph {
		graph[i] = [][2]int{}
	}
	for _, edge := range paths {
		from := edge[0]
		to := edge[1]
		weight := edge[2]
		// 无向图：加两条边
		graph[from] = append(graph[from], [2]int{to, weight})
		graph[to] = append(graph[to], [2]int{from, weight})
	}
	// [到达的点, 到达该点的电量]
	// 两个信息代表一个点（扩展出的）
	distance := make([][]int, n)
    visited := make([][]bool, n)
	for i := range distance {
		distance[i] = make([]int, cnt+1)
        visited[i] = make([]bool, cnt+1)
		for j := 0; j < cnt+1; j++ {
			distance[i][j] = MAX_INT
		}
	}
	minHeap := MinHeap{}
	distance[start][0] = 0
	heap.Push(&minHeap, [3]int{start, 0, 0})
	for len(minHeap) > 0 {
		record := heap.Pop(&minHeap).([3]int)
		cur := record[0]
		power := record[1]
		cost := record[2]
		if visited[cur][power] {
			continue
		}
		if cur == end {
			return cost
		}
		visited[cur][power] = true
		if power < cnt {
			// 只充一格电，之后如何抉择在下个循环中决定
			if !visited[cur][power+1] && cost+charge[cur] < distance[cur][power+1] {
				distance[cur][power+1] = cost + charge[cur]
				heap.Push(&minHeap, [3]int{cur, power + 1, cost + charge[cur]})
			}
		}
		for _, edge := range graph[cur] {
			// 不充电去别的城市
			nextCity := edge[0]
			restPower := power - edge[1]
			nextCost := cost + edge[1]
			if restPower >= 0 && !visited[nextCity][restPower] && nextCost < distance[nextCity][restPower] {
				distance[nextCity][restPower] = nextCost
				heap.Push(&minHeap, [3]int{nextCity, restPower, nextCost})
			}
		}
	}
	return -1
}
 
// [到达的点, 到达该点的电量, 花费时间]
type MinHeap [][3]int
 
func (h MinHeap) Len() int {
	return len(h)
}
 
func (h MinHeap) Less(i, j int) bool {
	return h[i][2] < h[j][2]
}
 
func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
 
func (h *MinHeap) Push(v any) {
	*h = append(*h, v.([3]int))
}
 
func (h *MinHeap) Pop() any {
	n := len(*h)
	res := (*h)[n-1]
	*h = (*h)[:n-1]
	return res
}

题目3.飞行路线 §

题目描述 §

Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 n 个城市设有业务，设这些城市分别标记为 0 到 n−1，一共有 m 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 k 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

测试链接 §

P4568【JLOI2011】飞行路线

思路 §

Dijkstra 算法的分层图最短路，扩出来的点：到达某个城市和当前使用了几次免单

答案 §

package main
 
import (
	"bufio"
	"container/heap"
	"fmt"
	"math"
	"os"
	"strconv"
)
 
const (
	MAXN    = 1e4 + 1
	MAXM    = 5e4<<1 + 1 // 无向图：记得边数加倍
	MAXK    = 11
	MAX_INT = math.MaxInt
)
 
var (
	n     int
	m     int
	k     int
	start int
	end   int
 
	head   = [MAXN]int{}
	next   = [MAXM]int{}
	to     = [MAXM]int{}
	weight = [MAXM]int{}
	cnt    = 1
 
	distance = [MAXN][MAXK]int{}
	visited  = [MAXN][MAXK]bool{}
	minHeap  = MinHeap{}
	heapSize = 0
)
 
func main() {
	// s := `5 6 1
	// 0 4
	// 0 1 5
	// 1 2 5
	// 2 3 5
	// 3 4 5
	// 2 3 3
	// 0 2 100`
	// in := bufio.NewScanner(strings.NewReader(s))
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		in.Scan()
		k, _ = strconv.Atoi(in.Text())
		in.Scan()
		start, _ = strconv.Atoi(in.Text())
		in.Scan()
		end, _ = strconv.Atoi(in.Text())
		build()
		a, b, c := 0, 0, 0
		for i := 0; i < m; i++ {
			in.Scan()
			a, _ = strconv.Atoi(in.Text())
			in.Scan()
			b, _ = strconv.Atoi(in.Text())
			in.Scan()
			c, _ = strconv.Atoi(in.Text())
			addEdge(a, b, c)
			addEdge(b, a, c)
		}
		fmt.Fprintln(out, dijkstra())
	}
	out.Flush()
}
 
func dijkstra() int {
	distance[start][0] = 0
	heap.Push(&minHeap, [3]int{start, 0, 0})
	for heapSize > 0 {
		record := heap.Pop(&minHeap).([3]int)
		cur := record[0]
		used := record[1]
		cost := record[2]
		if visited[cur][used] {
			continue
		}
		if cur == end {
			return cost
		}
		visited[cur][used] = true
		for i := head[cur]; i > 0; i = next[i] {
			nextCity := to[i]
			nextCost := weight[i]
			if used < k && !visited[nextCity][used+1] && distance[nextCity][used+1] > distance[cur][used] {
				// 用免费乘坐
				distance[nextCity][used+1] = distance[cur][used]
				heap.Push(&minHeap, [3]int{nextCity, used + 1, distance[nextCity][used+1]})
			}
			if !visited[nextCity][used] && distance[nextCity][used] > distance[cur][used]+nextCost {
				// 不用免费乘坐
				distance[nextCity][used] = distance[cur][used] + nextCost
				heap.Push(&minHeap, [3]int{nextCity, used, distance[nextCity][used]})
			}
		}
	}
	return -1
}
 
func build() {
	cnt = 1
	heapSize = 0
	for i := 0; i < n; i++ {
		head[i] = 0
		for j := 0; j <= k; j++ {
			distance[i][j] = MAX_INT
			visited[i][j] = false
		}
	}
}
 
func addEdge(f, t, w int) {
	next[cnt] = head[f]
	to[cnt] = t
	weight[cnt] = w
	head[f] = cnt
	cnt++
}
 
// [到达的点, 用了几次免费乘坐, 花费]
type MinHeap [MAXM * MAXK][3]int
 
func (MinHeap) Len() int {
	return heapSize
}
 
func (h MinHeap) Less(i, j int) bool {
	return h[i][2] < h[j][2]
}
 
func (h *MinHeap) Swap(i, j int) {
	h[i][0], h[j][0] = h[j][0], h[i][0]
	h[i][1], h[j][1] = h[j][1], h[i][1]
	h[i][2], h[j][2] = h[j][2], h[i][2]
}
 
func (h *MinHeap) Push(v any) {
	h[heapSize] = v.([3]int)
	heapSize++
}
 
func (h *MinHeap) Pop() any {
	heapSize--
	return h[heapSize]
}