题目描述

魔法阵

题解

看了一圈题解好像都用的 SPFA 和假堆优化dijkstra

本题就是一道有约束的分层图最短路问题，如果不了解分层图可以先百度了解一下（

跟分层图最短路不一样的是，本题有一个连续 k 短路不需要花费的一个约束条件，那么我们在传递状态的时候只需要特判一下，如果当前的已经使用了免费次数了，那么我们接下来我们松弛的时候就不需要花费。

这里我们使用一个二维数组 dis[i][k] 表示当前到达第 i 个节点，使用了 k 次免费次数的最短路径，那么我们可以得到状态转移方程：

不需要花费时：dis[v][k-1] = min(dis[v][k-1], dis[u][k]);

需要花费时：dis[v][k] = min(dis[v][k], dis[u][k] + w);

此外我们的 vis 数组也要二维

Code

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

public class Main {
    // 定义一些全局变量
    static int n, m, k, cnt;
    static final int maxn = 2000005, inf = 1047483647;

    // 定义边的数据结构
    static class node {
        int to, next, data;
    }

    // 定义边的数组
    static node[] edge = new node[maxn];

    // 添加边的函数
    static void add_edge(int from, int to, int data) {
        edge[++cnt] = new node();
        edge[cnt].to = to;
        edge[cnt].data = data;
        edge[cnt].next = head[from];
        head[from] = cnt;
    }

    // 定义距离数组和邻接表头数组
    static int[][] dis = new int[1005][15];
    static int[] head = new int[maxn];
    // 定义访问标记数组
    static boolean[][] vis = new boolean[1005][15];

    // 定义堆的数据结构
    static class heap {
        heap(int x, int y, int z) {
            node = x;
            data = y;
            step = z;
        }

        int node, data, step;
    }

    // Dijkstra算法的实现
    static void dijkstra() {
        // 初始化距离数组和访问标记数组
        for (int i = 0; i < 1005; i++) {
            Arrays.fill(vis[i], false);
            Arrays.fill(dis[i], inf);
        }
        dis[0][k] = 0;
        // 使用优先队列作为堆
        PriorityQueue<heap> q = new PriorityQueue<>((a, b) -> a.data - b.data);
        q.add(new heap(0, 0, k));
        while (!q.isEmpty()) {
            int now = q.peek().node;
            int step = q.peek().step;
            q.poll();
            if (vis[now][step])
                continue;
            vis[now][step] = true;
            for (int i = head[now]; i != 0; i = edge[i].next) {
                int to = edge[i].to, data = edge[i].data;

                // 如果已经使用了魔法，那么继续使用
                if (step < k && step > 0 && dis[to][step - 1] > dis[now][step]) {
                    dis[to][step - 1] = dis[now][step];
                    q.add(new heap(to, dis[to][step - 1], step - 1));
                }
                // 不使用魔法
                else if (step == k || step == 0) {
                    if (dis[to][step] > dis[now][step] + data) {
                        dis[to][step] = dis[now][step] + data;
                        q.add(new heap(to, dis[to][step], step));
                    }
                    // 如果还没有用过，尝试下一步使用魔法
                    if (step == k && dis[to][step - 1] > dis[now][step]) {
                        dis[to][step - 1] = dis[now][step];
                        q.add(new heap(to, dis[to][step - 1], step - 1));
                    }
                }
            }
        }
    }

    // 主函数
    static public void main(String[] args) throws Exception {
        Read sc = new Read();
        n = sc.nextInt();
        k = sc.nextInt();
        m = sc.nextInt();

        // 读入边的信息并添加边
        while (m-- > 0) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            add_edge(x, y, z);
            add_edge(y, x, z);
        }
        // 运行Dijkstra算法
        dijkstra();
        // 输出结果
        System.out.println(Math.min(dis[n - 1][k], dis[n - 1][0]));
    }
}

// 定义读入类
class Read {
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public int nextInt() throws Exception {
        st.nextToken();
        return (int) st.nval;
    }
}

end