$$\color{Red}{第K短路—【A star】【各种边界问题和剪枝策略全解】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

这道题是A * 算法。

1. 首先，A star 算法是利用启发信息对 Dijkstra 算法的一种拓展，所以本质还是利用 堆排序 和 单调性 思想。
2. 本题我们求的并不是单纯的最短路，而是第K短路。而选用了Dijkstra先反算一遍的的距离作为启发信息。
3. A star 算法的思路 ——> 即：定义一个状态 f = d + g，d是启发信息，或者说估价函数，而g是实际距离，我们每次更新沿用Dijkstra算法的思路，以最优的f节点更新它的邻居节点，并同步更新g实际距离

1. 为什么使用反向Dijkstra 作为启发？

因为 Dijkstra 算的是各个点到源点的最短路，我们正向算的话，求得是各点到起点的距离，而不是到终点的距离。

2. 为什么当起点等于终点 需要自增 K？

这道题限制每条最短路需要至少含有一条边，而当起点和终点相同的情况下，其实内部存在一条长度为0的没有边的最短路，即开局即出队，但这个答案和题目限制的必须存在一条边冲突，故K自增，相当于把这个答案排除，我们求K+1即是合法的第K个

3. 为什么出现一个剪枝策略，当cnt[son] <= k才能进入A star的队列？

任何节点当出队K+1次的时候，要么更新不到终点，此时利用它更新的节点的一层层信息是无用的

反证法：【假设图中无环】一个点已经K+1次出队，且它是能够更新到终点的节点

和队列单调性矛盾

如果它能更新到终点，在它N次出队后，势必终点的第N次出队会先于它的第N+1次出队

【其实存在如果有节点数很小的环，让它在短期内再次入队且先于终点出队的情况】

但是可以试想一下，如果它能走到终点，当它入队满足N次，势必前面的N次之后，就可以更新到终点第N次出队了，没必要再让它入队，【此时必然第N次出队快于它带来的一层层BFS更新的那些新的点更新终点】降低我们搜索的效率了。

如果不是这种情况，即根本走不到终点，那么让它入队就完全是无效节点，还会带来一堆无效节点，故也没必要入队

4. 那么该如何确定第 K 短路？

——》单调性——》终点出去第K次

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {

    static int N = 1010, M = 20010;
    static int n, m, k, start, end, idx;
    static int[] h = new int[N];
    static int[] rh = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];

    static int[] d = new int[M];
    static boolean[] st = new boolean[N];
    static int[] cnt = new int[M];

    static void add(int[] h, int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }

    static void dijkstra() {
        PriorityQueue<int[]> q = new PriorityQueue<>(((o1, o2) -> o1[1] - o2[1]));
        Arrays.fill(d, 0x3f3f3f3f);
        q.add(new int[]{end, 0});
        d[end] = 0;
        while (!q.isEmpty()) {
            int[] father = q.remove();
            int num = father[0];
            if (st[num]) continue;
            st[num] = true;
            for (int i = rh[num]; i != -1; i = ne[i]) {
                int son = e[i];
                int c = w[i];
                if (d[son] > d[num] + c) {
                    d[son] = d[num] + c;
                    q.add(new int[]{son, d[son]});
                }
            }
        }
    }

    static int aStar() {
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        q.add(new int[]{start, d[start] + 0, 0});

        while (!q.isEmpty()) {
            int[] father = q.remove();
            int num = father[0];
            cnt[num]++;
            if (num == end && cnt[num] == k) return father[2];

            for (int i = h[num]; i != -1; i = ne[i]) {
                int son = e[i];
                int c = w[i];
                if (cnt[son] <= k) {
                    q.add(new int[]{son, d[son] + father[2] + c, father[2] + c});
                }
            }
        }
        return -1;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        Arrays.fill(h, -1);
        Arrays.fill(rh, -1);
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(h, a, b, c);
            add(rh, b, a, c);
        }

        String[] s3 = br.readLine().split(" ");
        start = Integer.parseInt(s3[0]);
        end = Integer.parseInt(s3[1]);
        k = Integer.parseInt(s3[2]);
        // 为了保证每条最短路至少包含一条边
        if (start == end) k++;

        dijkstra();
        System.out.println(aStar());
    }
}