dj适用的情景

给定一个源点, 求解源点到每个点的最短路径 (单源最短路径算法)
适用于: 有向图和边的权值不能为负值

此处没有介绍反向索引堆的解法
使用最常用的普通堆 + 建图

模板题(网络延迟时间)

链接: https://leetcode.cn/problems/network-delay-time/description/

题目步骤解析

1. 开始先将所有点的距离都设为无穷大, 开始所有点都没有使用过, 所以大小先都设为无穷大, 并且之后我们要进行弹出操作, 弹出的点不需要再进行添加, 所以需要 vis 来进行标记操作
2. 接下来将所需源点添加入堆中, 开始 a 到 a 的距离是 0, distance 的位置更新成 0, 进入堆中并弹出, 并将 a 点标记为 true, 将 a 指向的边添加到堆中, 前提是没有被标记过, 并且到那个点的距离要比记录在distance 上的距离要小 , 才可以添加到堆中
3. 当将 a 指向的点全部遍历完, 继续弹出第一个点, 并重复以上操作, 就可以得到一张到 a 到 各个点的最短距离的数据, 我们进行遍历, 查找是否存在无穷大, 如果有说明无法到达这个点, 如果没有就说明可以找到最小值

代码(附上解析)

动态建图版

public int networkDelayTime(int[][] times, int n, int k) {
        // 动态建图
        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
        for(int i = 0;i <= n;i++) {
            graph.add(new ArrayList<>());
        }
        // 0 是出发点, 1 是到达点, 2 是距离
        for(int[] edge : times) {
            graph.get(edge[0]).add(new int[]{edge[1],edge[2]});
        }
        // 构建路线(多1一个位置是因为0位置我们不使用)
        int[] distance = new int[n + 1];
        // 开始标记无穷大
        Arrays.fill(distance,Integer.MAX_VALUE);
        // 构造访问的数组, 防止重复访问
        boolean[] vis = new boolean[n + 1];
        // 构造小根堆
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        // 源点标记一下距离为 0, 并添加到小根堆中 
        distance[k] = 0;
        heap.add(new int[]{k,0});
        // 当堆中没有元素就退出
        while (!heap.isEmpty()) {
            // 弹出首个点, 值已经在之前更新了, 不需要更新, 我们只需要遍历该点到达的地方
            int u = heap.poll()[0];
            // 访问过直接跳过这个点
            if(vis[u]){
                continue;
            }
            // 没弹出过标记一下
            vis[u] = true;
            // 开始遍历这个点到达的所有点
            for (int[] edge : graph.get(u)) {
                int a = edge[0];// 代表到达点
                int b = edge[1];// 代表距离
                // 更新并添加的前提, 到达点未被弹出, 并且从弹出的出发点到达(到达点)的距离要更小才会进行更新
                if(!vis[a] && distance[u] + b < distance[a]) {
                    distance[a] = distance[u] + b;
                    heap.add(new int[]{a,distance[a]});
                }
            }
        }
        // 返回值一定要找到最大值, 因为我们存储的是到达每个点的最小距离
        int ans = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++) {
            // 如果发现无穷大, 无法到达所有点
            if(distance[i] == Integer.MAX_VALUE) {
                return -1;
            }
            // 更新最大值
            ans = Math.max(distance[i],ans);
        }
        return ans;
    }

链式前向星

public static int MAXN = 101;
public static int MAXM = 6001;
public static int[] head = new int[MAXN];// 边号 出发点
public static int[] next = new int[MAXM];// 下一个的边号 边号
public static int[] to = new int[MAXM];// 到达点 边号
public static int[] weight = new int[MAXM];// 距离 边号
public static int cnt = 1;
public static int networkDelayTime1(int[][] times, int n, int k) {
    // 链式前向星建图
    // 0 是出发点, 1 是到达点, 2 是距离
    for(int[] edge : times) {
        build(edge[0],edge[1],edge[2]);
    }
    // 构建路线(多1一个位置是因为0位置我们不使用)
    int[] distance = new int[n + 1];
    // 开始标记无穷大
    Arrays.fill(distance,Integer.MAX_VALUE);
    // 构造访问的数组, 防止重复访问
    boolean[] vis = new boolean[n + 1];
    // 构造小根堆
    PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
    // 源点标记一下距离为 0, 并添加到小根堆中
    distance[k] = 0;
    heap.add(new int[]{k,0});
    // 当堆中没有元素就退出
    while (!heap.isEmpty()) {
        // 弹出首个点, 值已经在之前更新了, 不需要更新, 我们只需要遍历该点到达的地方
        int u = heap.poll()[0];
        // 访问过直接跳过这个点
        if(vis[u]){
            continue;
        }
        // 没弹出过标记一下
        vis[u] = true;
        // 开始遍历这个点到达的所有点
        // 先从 head 找到该点的第一个边号, 并遍历所有的边号
        for (int i = head[u]; i != 0; i = next[i]) {
            int a = to[i];// 代表到达点
            int b = weight[i];// 代表距离
            // 更新并添加的前提, 到达点未被弹出, 并且从弹出的出发点到达(到达点)的距离要更小才会进行更新
            if(!vis[a] && distance[u] + b < distance[a]) {
                distance[a] = distance[u] + b;
                heap.add(new int[]{a,distance[a]});
            }
        }



    }
    // 返回值一定要找到最大值, 因为我们存储的是到达每个点的最小距离
    int ans = Integer.MIN_VALUE;
    for(int i = 1;i <= n;i++) {
        // 如果发现无穷大, 无法到达所有点
        if(distance[i] == Integer.MAX_VALUE) {
            return -1;
        }
        // 更新最大值
        ans = Math.max(distance[i],ans);
    }
    return ans;
}

private static void build(int a, int b, int c) {
    // 如果 head[a] 开始存着一条边号, 要把它作为下一条边号
    // 并更新一下 head[a] 的新边号
    next[cnt] = head[a];
    head[a] = cnt;
    // 更新一下这条边对应的点和权值
    to[cnt] = b;
    weight[cnt++] = c;
}

静态建图会比动态建图速度快一半

单源最短路径

链接: https://www.luogu.com.cn/problem/P4779
洛谷的测试用例大, 用链式前向星来建图

解析

这里就不多赘述, 因为和上一题基本完全一样, 只是必须要使用链式前向星来建图

代码

import java.io.*;
import java.util.*;

public class 单源最短路径 {
    public static PrintWriter out = new PrintWriter(
            new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read in = new Read();
    public static int MAXN = 100001;
    public static int MAXM = 200001;
    public static int[] head = new int[MAXN];
    public static int[] next = new int[MAXM];
    public static int[] to = new int[MAXM];
    public static int[] weight = new int[MAXM];
    public static int n;
    public static int m;
    public static int cnt = 1;
    public static void main(String[] args) throws IOException{
        n = in.nextInt();
        m = in.nextInt();
        int s = in.nextInt();
        // 链式前向星建图
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            addEdge(a,b,c);
        }
        // 建立 distance 和 vis
        int[] distance = new int[n + 1];
        Arrays.fill(distance,Integer.MAX_VALUE);
        boolean[] vis = new boolean[n + 1];
        // 源点的距离标记
        distance[s] = 0;
        // 堆的建立以及加入源点
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        heap.offer(new int[]{s,0});
        while (!heap.isEmpty()) {
            // 弹出第一个点, 获取到达点的值
            int u = heap.poll()[0];
            if (vis[u]) {
                continue;
            }
            vis[u] = true;
            // 遍历图更新 distance 并加入堆中
            for (int i = head[u]; i != 0; i = next[i]) {
                int a = to[i]; // 到达点
                int b = weight[i]; // 距离
                // 没访问过并且要小于到达点的距离
                if (!vis[a] && distance[u] + b < distance[a]) {
                    distance[a] = distance[u] + b;
                    heap.offer(new int[]{a, distance[a]});
                }
            }
        }
        // 打印
        for (int i = 1; i <= n; i++) {
            out.print(distance[i] + " ");
        }
        out.close();
    }

    private static void addEdge(int a, int b, int c) {
        next[cnt] = head[a];
        head[a] = cnt;
        to[cnt] = b;
        weight[cnt++] = c;
    }


    public static class Read{
        StringTokenizer st = new StringTokenizer("");
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String next() throws IOException
        {
            while(!st.hasMoreTokens())
            {
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }

        String nextLine() throws IOException
        {
            return bf.readLine();
        }

        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}

可以优化的地方是使用反向索引堆, 自己建堆时间还可以更快一点

最小体力消耗路径

链接: https://leetcode.cn/problems/path-with-minimum-effort/description/

题目解析

想象成dj问题, 源点到每个点的最小距离, 转化成整条路径的最大距离, 所以我们更新 distance 的距离的时候, 需要先对出发点和到达点的位置相减, 然后与 出发点的最小距离进行比较, 也就是

int nc = Math.max(Math.abs(heights[a][b] - heights[x][y]),c);

这是和之前唯一不同的地方, 以及需要加入 bfs 来进行层度优先遍历来进行搜索

代码

import java.util.Arrays;
import java.util.PriorityQueue;

public class 最小体力消耗路径_dj {
    public static int[] move = {1,0,-1,0,1};
    public int minimumEffortPath(int[][] heights) {
        // 先求出 n 和 m 方便使用
        // 分析求出源点到每个点的最小距离
        int n = heights.length;
        int m = heights[0].length;
        // 源点到每个点的最短距离, 更新的时候要更新成路径的最大值
        int[][] distance = new int[n][m];
        for(int[] a : distance){
            Arrays.fill(a,Integer.MAX_VALUE);
        }
        // 源点的距离
        distance[0][0] = 0;
        // 标记路线是否走过
        boolean[][] vis = new boolean[n][m];
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2] - b[2]);
        heap.add(new int[]{0,0,0});
        while (!heap.isEmpty()) {
            int[] t = heap.poll();
            int a = t[0]; // i
            int b = t[1]; // j
            int c = t[2]; // 距离也就是到每个点需要的代价
            // 剪枝, 找到该点直接返回即可
            if(a == n - 1 && b == m - 1){
                return c;
            }
            // 访问过的点不再访问
            if (vis[a][b]) {
                continue;
            }
            vis[a][b] = true;
            // 上下左右四个方向移动
            for (int i = 0; i < 4; i++) {
                int x = a + move[i];// 横坐标
                int y = b + move[i + 1];// 纵坐标
                // 先判断是否越界
                if(x >= 0 && y >= 0 && x < n && y < m && !vis[x][y]){
                    // 更新一下该路径的最大值
                    int nc = Math.max(Math.abs(heights[a][b] - heights[x][y]),c);
                    // 如果该点小于存储的距离, 更新并丢到堆中
                    if(nc  < distance[x][y]){
                        distance[x][y] = nc;
                        heap.offer(new int[]{x,y,distance[x][y]});
                    }
                }
            }
        }
        // 都找不到就返回 -1, 理论上一定可以找到, 防止编译器报错
        return -1;
    }
}

水位上升的泳池中游泳

链接: https://leetcode.cn/problems/swim-in-rising-water/description/

题目解析

题目和上一题基本完全一样, 唯一的区别就是此次的源点距离不为 0 (我开始就错了), 因为要等 t 时刻到达源点的高度才可以开始向各个方向移动, 其他与上一题一般无二, 可以来练练手

代码

import java.util.Arrays;
import java.util.PriorityQueue;

public class 水位上升的泳池中游泳 {
    public static int[] move = {1,0,-1,0,1};
    public int swimInWater(int[][] grid) {
        // 构造一下距离和 vis
        int n = grid.length;
        int m = grid[0].length;
        int[][] distance = new int[n][m];
        for (int[] a : distance){
            Arrays.fill(a,Integer.MAX_VALUE);
        }
        boolean[][] vis = new boolean[n][m];
        distance[0][0] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2]-b[2]);
        heap.offer(new int[]{0,0,grid[0][0]});
        while (!heap.isEmpty()) {
            int[] t = heap.poll();
            int a = t[0]; // i
            int b = t[1]; // j
            int c = t[2]; // 到 b 点所需要的代价
            if (a == n - 1 && b== m - 1) {
                return c;
            }
            if (vis[a][b]) {
                continue;
            }
            vis[a][b] = true;
            for (int i = 0; i < 4; i++) {
                int x = a + move[i];
                int y = b + move[i + 1];
                if (x >= 0 && y >= 0 && x < n && y < m && !vis[x][y]) {
                    int nc = Math.max(grid[x][y],c);
                    if(nc < distance[x][y]) {
                        distance[x][y] = nc;
                        heap.offer(new int[]{x,y,nc});
                    }
                }
            }
        }
        return -1;
    }
}

分层图最短路径先欠一下

不把实际位置看做图上的点，而是把实际位置及其状态的组合看做是图上的点, 然后搜索 bfs 或者 dj 的过程不变, , 只是扩了点(分层)而已原理简单, 核心在于如何扩点、如何到达、如何算距离, 每个题可能都不一样

获取所有钥匙的最短路径

链接: https://leetcode.cn/problems/shortest-path-to-get-all-keys/description/

题目分析

以一个我之前一直通不过的一个用例来大概讲解一下题目思路

1. 开始时字符串数组, 我们需要先转化成字符数组比较好操作, 顺带找到源点, 并找到钥匙
2. 此处钥匙的状态我们使用 int 的前 6 位来进行标记, 1 为有钥匙, 0 为没钥匙
3. 然后分层图遍历, 相当于点可以重复走, 但是此时你的状态要是不同, 如上图, 当你拿到了钥匙 b, 你可以选择往回走, 因为你没钥匙的时候走到 b 格子, 和 有钥匙的时候走回去 @ 格子, 是不一样的状态, 这是分层图最短路径的核心, 最关键就是状态不一样
4. 然后我们对走到各种格子的情况进行划分
   • 走到 . 格子, 直接标记并添加队列即可
   • 走到 # 格子, 不可以走, 标记一下
   • 走到 锁 的话, 查看一下手上有没有钥匙, 如果有钥匙就添加队列并标记
   • 走到 钥匙 的话, 把钥匙的状态更新一下, 然后看一下是否已经拿到所有钥匙了, 拿到了就返回, 没拿到就标记加上添加到队列里
   • 走到 @ 格子, 只需要看一下有没有走过即可, 状态不同就可以走, 并标记

代码

public class 获取所有钥匙的最短路径 {
    public static int MAXN = 31;
    public static char[][] grid = new char[3][5];
    public static boolean[][][] vis = new boolean[3][5][64];
    public static int[][] queue = new int[3 * 5 * 64][3];
    public static int n,m;
    public static int l,r;
    public static int[] move = {1,0,-1,0,1};
    public static int shortestPathAllKeys(String[] grids) {
        n = grids.length;
        m = grids[0].length();
        l = r = 0;
        int keys = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = grids[i].charAt(j);
                if (grid[i][j] == '@') {
                    add(i, j, 0);
                    vis[i][j][0] = true;
                }
                if (grid[i][j] >= 'A' && grid[i][j] <= 'F') {
                    keys |= (1 << (grid[i][j] - 'A'));
                }
            }
        }
        int ans = 0;

        while (l < r) {
            int size = r - l;
            ans++;
            while (size-- > 0) {
                int[] t = queue[l++];
                int a = t[0];
                int b = t[1];
                int c = t[2];
                for (int i = 0; i < 4; i++) {
                    int x = a + move[i];
                    int y = b + move[i + 1];
                    if (x >= 0 && y >= 0 && x < n && y < m && !vis[x][y][c]) {
                        // 找到空房间
                        if (grid[x][y] == '.') {
                            add(x, y, c);
                            vis[x][y][c] = true;
                        } else if (grid[x][y] >= 'A' && grid[x][y] <= 'F') {
                            // 找到锁
                            if (((1 << (grid[x][y] - 'A')) & c) != 0) {
                                add(x, y, c);
                            }
                            vis[x][y][c] = true;
                        } else if (grid[x][y] >= 'a' && grid[x][y] <= 'f') {
                            int nc = (1 << (grid[x][y] - 'a')) | c;
                            if (nc == keys) {
                                return ans;
                            }
                            add(x, y, nc);
                            vis[x][y][nc] = true;
                        } else if (grid[x][y] == '#') {
                            vis[x][y][c] = true;
                        } else if (grid[x][y] == '@') {
                            add(x,y,c);
                            vis[x][y][c] = true;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < r; i++) {
            System.out.println("第" + (i + 1) +"次 "+ "i = " + queue[i][0] + " ,j = " + queue[i][1] + ",c = "+ queue[i][2]);
            System.out.println();
        }
        return -1;
    }
    private static void add(int i, int j, int k) {
        queue[r][0] = i;
        queue[r][1] = j;
        queue[r++][2] = k;
    }

    public static void main(String[] args) {
        String[] grid = {
                "@...a",
                ".###A",
                "b.BCc"
        };
        System.out.println(shortestPathAllKeys(grid));
    }

}

优雅一点版本代码

public static int MAXN = 31;
public static char[][] grid = new char[3][5];
public static boolean[][][] vis = new boolean[3][5][64];
public static int[][] queue = new int[3 * 5 * 64][3];
public static int n,m;
public static int l,r;
public static int[] move = {1,0,-1,0,1};
public static int shortestPathAllKeys(String[] grids) {
    n = grids.length;
    m = grids[0].length();
    l = r = 0;
    // 找到钥匙, 因为钥匙只有 6 把, 所以使用 int 的前 6 位来进行表示
    int keys = 0;
    // 字符串数组太恶心了, 使用填一下表格, 并找出所有的钥匙, 并添加源点到队列里
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            grid[i][j] = grids[i].charAt(j);
            if (grid[i][j] == '@') {
                add(i, j, 0);
                // 标记这个点已经走过了
                vis[i][j][0] = true;
            }
            if (grid[i][j] >= 'A' && grid[i][j] <= 'F') {
                // 位运算添加
                keys |= (1 << (grid[i][j] - 'A'));
            }
        }
    }
    // 最终的结果
    int ans = 0;

    while (l < r) {
        int size = r - l;
        ans++;
        int a,b,c;
        while (size-- > 0) {
            a = queue[l][0]; // 坐标 i
            b = queue[l][1]; // 坐标 j
            c = queue[l++][2]; // 钥匙的状态
            for (int i = 0; i < 4; i++) {
                int x = a + move[i];
                int y = b + move[i + 1];
                int nc = c;
                if (x < 0 || y < 0 || x == n || y == m || vis[x][y][c] || grid[x][y] == '#') {
                    // 遇到墙或者是越界
                    continue;
                }
                if (grid[x][y] >= 'A' && grid[x][y] <= 'F' && ((1 << (grid[x][y] - 'A')) & nc) == 0) {
                    // 找到锁没有对应的钥匙
                    continue;
                }
                if (grid[x][y] >= 'a' && grid[x][y] <= 'f') {
                    // 是一把锁
                    nc = (1 << (grid[x][y] - 'a')) | c;
                }
                if (nc == keys) {
                    return ans;
                }
                if (!vis[x][y][c]) {
                    add(x, y, nc);
                }
            }
        }
    }
    return -1;
}

电动车游城市

链接: https://leetcode.cn/problems/DFPeFJ/

题目分析

1. 此题我们还是采用分层图遍历, 加上电量一层, 采用 dj 来进行求解, 因为这道题让我们求 start 到 end 的最小单位时间, 所以我们采用 dj
2. 先确定 distance 和 vis, 因为每个电量都算一层, 电量最多为 cnt 不可能能超过
   • distance[n][cnt + 1] 设置到每个点在某个电量的最短距离
   • vis[n][cnt + 1] 检查每个点是否被访问过, 避免重复访问
3. 每次到达一个状态, 分为两种情况
   • 在此地充一格电 (因为要枚举出所有的情况, 所以不充两格,三格点), 看一下有没有访问过了, 并且和存的最小值进行比较, 如果更小的话就更新并添加到堆中
   • 直接前往下一个地点, 前提需要电够用, 其次就是看一下有没有访问过, 然后与所存的最小值进行比较, 更新并添加到堆中

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class 电动车游城市 {
    public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
        // 建图, 采用动态建图的方式
        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
        int n = charge.length;
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] path: paths) {
            graph.get(path[0]).add(new int[]{path[1],path[2]});
            graph.get(path[1]).add(new int[]{path[0],path[2]});
        }
        // 采用 dj 算法, 一样设置一个 distance 来进行记录到每个点的每个电量的距离
        int[][] distance = new int[n][cnt + 1];
        // 最开始出发的点电量为 0 并且 需要的时间也为 0
        distance[start][0] = 0;
        // 访问记录, 防止重复访问
        boolean[][] vis = new boolean[n][cnt + 1];
        // 开始全都是无穷大
        for (int[] a : distance) {
            Arrays.fill(a,Integer.MAX_VALUE);
        }
        // 0 : 当前点
        // 1 : 来到当前点的电量
        // 2 : 花费时间
        // 堆 + 比较器
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2] - b[2]);
        heap.offer(new int[]{start,0,0});
        while (!heap.isEmpty()) {
            // 每次弹出一个
            int[] record = heap.poll();
            int cur = record[0]; // 点
            int power = record[1]; // 电量
            int cost = record[2]; // 花费的时间
            if (vis[cur][power]) {
                continue;
            }
            // 剪枝加快速度
            if (cur == end) {
                // 发现终点, 直接返回
                return cost;
            }
            vis[cur][power] = true;
            // 充电
            if (power < cnt) {
                // cnt, power + 1 每次充一格电, 并更新, 和最开始的模板其实差不多
                if (!vis[cur][power + 1] && cost + charge[cur] < distance[cur][power + 1]) {
                    distance[cur][power + 1] = cost + charge[cur];
                    heap.add(new int[]{cur,power + 1,cost + charge[cur]});
                }
            }
            for (int[] edge : graph.get(cur)) {
                // 不充电去别的城市
                int nextCity = edge[0];
                int restPower = power - edge[1];
                int nextCost = cost + edge[1];
                if (restPower >= 0 && !vis[nextCity][restPower] && nextCost < distance[nextCity][restPower]) {
                    distance[nextCity][restPower] = nextCost;
                    heap.add(new int[]{nextCity,restPower,nextCost});
                }
            }
        }
        return -1;
    }
}

飞行路线

链接: https://www.luogu.com.cn/problem/P4568

题目分析

这道题和上一道其实一模一样, 甚至还要更简单一点, 我们还是分层图进行遍历, 他还是从 start 到达 end, 还是采取最短路径的方式, 但是我们以免费的次数为层数进行遍历, 其他大差不差

唯一区别, 洛谷的题目要求比较高, 我们不能使用动态建图的方式, 我们需要使用链式前向星来进行建图, 以及这题是双向的, 不是单向图(排错发现是自己建成单向图了)

代码

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class 飞行路线 {
    public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read in = new Read();
    public static int MAXN = 10001;
    public static int MAXM = 100001;
    public static int[] head = new int[MAXN];
    public static int[] next = new int[MAXM];
    public static int[] to = new int[MAXM];
    public static int[] weight = new int[MAXM];
    public static int cnt;
    public static void main(String[] args) throws IOException {
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        int start = in.nextInt();
        int end = in.nextInt();
        // 建图
        cnt = 1;
        while (m-- > 0){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            // 一定要建双向图
            addEdge(a,b,c);
            addEdge(b,a,c);
        }

        // 到每个点的最小花费, n 是点 k 是使用了免费
        int[][] distance = new int[n][k + 1];
        for (int[] a : distance) {
            Arrays.fill(a,Integer.MAX_VALUE);
        }
        boolean[][] vis = new boolean[n][k + 1];
        distance[start][0] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2] - b[2]);
        heap.add(new int[]{start,0,0});
        while (!heap.isEmpty()) {
            int[] t = heap.poll();
            int u = t[0];
            int use = t[1];
            int cost = t[2];
            if (vis[u][use]) {
                continue;
            }
            if (u == end) {
                out.println(cost);
                out.close();
                return;
            }
            vis[u][use] = true;
            for (int i = head[u]; i != 0; i = next[i]) {
                int v = to[i]; // 到达的下一个点
                int w = weight[i]; // 需要的代价
                // 免费一次
                if (use < k && distance[u][use] <  distance[v][use + 1]) {
                    distance[v][use + 1] = distance[u][use];
                    heap.add(new int[]{v,use + 1,distance[v][use + 1]});
                }
                // 不免费
                if (distance[u][use] + w < distance[v][use]) {
                    distance[v][use] = distance[u][use] + w;
                    heap.add(new int[]{v,use,distance[v][use]});
                }
            }
        }
        out.print(-1);
        out.close();
    }

    private static void addEdge(int a, int b, int c) {
        next[cnt] = head[a];
        head[a] = cnt;
        to[cnt] = b;
        weight[cnt++] = c;
    }


    public static class Read // 自定义快速读入
    {
        StringTokenizer st = new StringTokenizer("");
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String next() throws IOException
        {
            while(!st.hasMoreTokens())
            {
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }

        String nextLine() throws IOException
        {
            return bf.readLine();
        }

        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}