AI 助理
备案控制台
开发者社区 人工智能 文章 正文

class064 Dijkstra算法、分层图最短路【算法】

2023-12-21 65
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： class064 Dijkstra算法、分层图最短路【算法】

class064 Dijkstra算法、分层图最短路【算法】

算法讲解064【必备】Dijkstra算法、分层图最短路

code1 743. 网络延迟时间

// Dijkstra算法模版（Leetcode）

// 网络延迟时间

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

// 给你一个列表 times，表示信号经过 有向 边的传递时间

// times[i] = (ui, vi, wi)，表示从ui到vi传递信号的时间是wi

// 现在，从某个节点 s 发出一个信号

// 需要多久才能使所有节点都收到信号

// 如果不能使所有节点收到信号，返回 -1

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

code1 P4779 【模板】单源最短路径（标准版）

// Dijkstra算法模版（洛谷）

// 静态空间实现 : 链式前向星 + 反向索引堆

// 测试链接 : https://www.luogu.com.cn/problem/P4779

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下所有代码，把主类名改成Main，可以直接通过

package class064;
// Dijkstra算法模版（洛谷）
// 静态空间实现 : 链式前向星 + 反向索引堆
// 测试链接 : https://www.luogu.com.cn/problem/P4779
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Code01_DijkstraLuogu {
  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 cnt;
  // 反向索引堆
  public static int[] heap = new int[MAXN];
  // where[v] = -1，表示v这个节点，从来没有进入过堆
  // where[v] = -2，表示v这个节点，已经弹出过了
  // where[v] = i(>=0)，表示v这个节点，在堆上的i位置
  public static int[] where = new int[MAXN];
  public static int heapSize;
  public static int[] distance = new int[MAXN];
  public static int n, m, s;
  public static void build() {
    cnt = 1;
    heapSize = 0;
    Arrays.fill(head, 1, n + 1, 0);
    Arrays.fill(where, 1, n + 1, -1);
    Arrays.fill(distance, 1, n + 1, Integer.MAX_VALUE);
  }
  // 链式前向星建图
  public static void addEdge(int u, int v, int w) {
    next[cnt] = head[u];
    to[cnt] = v;
    weight[cnt] = w;
    head[u] = cnt++;
  }
  public static void addOrUpdateOrIgnore(int v, int w) {
    if (where[v] == -1) {
      heap[heapSize] = v;
      where[v] = heapSize++;
      distance[v] = w;
      heapInsert(where[v]);
    } else if (where[v] >= 0) {
      distance[v] = Math.min(distance[v], w);
      heapInsert(where[v]);
    }
  }
  public static void heapInsert(int i) {
    while (distance[heap[i]] < distance[heap[(i - 1) / 2]]) {
      swap(i, (i - 1) / 2);
      i = (i - 1) / 2;
    }
  }
  public static int pop() {
    int ans = heap[0];
    swap(0, --heapSize);
    heapify(0);
    where[ans] = -2;
    return ans;
  }
  public static void heapify(int i) {
    int l = 1;
    while (l < heapSize) {
      int best = l + 1 < heapSize && distance[heap[l + 1]] < distance[heap[l]] ? l + 1 : l;
      best = distance[heap[best]] < distance[heap[i]] ? best : i;
      if (best == i) {
        break;
      }
      swap(best, i);
      i = best;
      l = i * 2 + 1;
    }
  }
  public static boolean isEmpty() {
    return heapSize == 0;
  }
  public static void swap(int i, int j) {
    int tmp = heap[i];
    heap[i] = heap[j];
    heap[j] = tmp;
    where[heap[i]] = i;
    where[heap[j]] = j;
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken(); m = (int) in.nval;
      in.nextToken(); s = (int) in.nval;
      build();
      for (int i = 0, u, v, w; i < m; i++) {
        in.nextToken(); u = (int) in.nval;
        in.nextToken(); v = (int) in.nval;
        in.nextToken(); w = (int) in.nval;
        addEdge(u, v, w);
      }
      dijkstra();
      out.print(distance[1]);
      for (int i = 2; i <= n; i++) {
        out.print(" " + distance[i]);
      }
      out.println();
    }
    out.flush();
    out.close();
    br.close();
  }
  public static void dijkstra() {
    addOrUpdateOrIgnore(s, 0);
    while (!isEmpty()) {
      int v = pop();
      for (int ei = head[v]; ei > 0; ei = next[ei]) {
        addOrUpdateOrIgnore(to[ei], distance[v] + weight[ei]);
      }
    }
  }
}

code2 1631. 最小体力消耗路径

// 最小体力消耗路径

// 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights

// 其中 heights[row][col] 表示格子 (row, col) 的高度

// 一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1)

// （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动

// 你想要找到耗费 体力 最小的一条路径

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

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

// 测试链接 ：https://leetcode.cn/problems/path-with-minimum-effort/

package class064;
import java.util.PriorityQueue;
// 最小体力消耗路径
// 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights
// 其中 heights[row][col] 表示格子 (row, col) 的高度
// 一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) 
// （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动
// 你想要找到耗费 体力 最小的一条路径
// 一条路径耗费的体力值是路径上，相邻格子之间高度差绝对值的最大值
// 请你返回从左上角走到右下角的最小 体力消耗值
// 测试链接 ：https://leetcode.cn/problems/path-with-minimum-effort/
public class Code02_PathWithMinimumEffort {
  // 0:上，1:右，2:下，3:左
  public static int[] move = new int[] { -1, 0, 1, 0, -1 };
  public int minimumEffortPath(int[][] heights) {
    // (0,0)源点
    // -> (x,y)
    int n = heights.length;
    int m = heights[0].length;
    int[][] distance = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        distance[i][j] = Integer.MAX_VALUE;
      }
    }
    distance[0][0] = 0;
    boolean[][] visited = new boolean[n][m];
    // 0 : 格子的行
    // 1 : 格子的列
    // 2 : 源点到当前格子的代价
    PriorityQueue<int[]> heap = new PriorityQueue<int[]>((a, b) -> a[2] - b[2]);
    heap.add(new int[] { 0, 0, 0 });
    while (!heap.isEmpty()) {
      int[] record = heap.poll();
      int x = record[0];
      int y = record[1];
      int c = record[2];
      if (visited[x][y]) {
        continue;
      }
      if (x == n - 1 && y == m - 1) {
        // 常见剪枝
        // 发现终点直接返回
        // 不用等都结束
        return c;
      }
      visited[x][y] = true;
      for (int i = 0; i < 4; i++) {
        int nx = x + move[i];
        int ny = y + move[i + 1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
          int nc = Math.max(c, Math.abs(heights[x][y] - heights[nx][ny]));
          if (nc < distance[nx][ny]) {
            distance[nx][ny] = nc;
            heap.add(new int[] { nx, ny, nc });
          }
        }
      }
    }
    return -1;
  }
}

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

// 水位上升的泳池中游泳

// 在一个 n x n 的整数矩阵 grid 中

// 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度

// 当开始下雨时，在时间为 t 时，水池中的水位为 t

// 你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台

// 假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的

// 当然，在你游泳的时候你必须待在坐标方格里面。

// 你从坐标方格的左上平台 (0，0) 出发

// 返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间

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

package class064;
import java.util.PriorityQueue;
// 水位上升的泳池中游泳
// 在一个 n x n 的整数矩阵 grid 中
// 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度
// 当开始下雨时，在时间为 t 时，水池中的水位为 t
// 你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台
// 假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的
// 当然，在你游泳的时候你必须待在坐标方格里面。
// 你从坐标方格的左上平台 (0，0) 出发
// 返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间
// 测试链接 : https://leetcode.cn/problems/swim-in-rising-water/
public class Code03_SwimInRisingWater {
  // 0:上，1:右，2:下，3:左
  public static int[] move = new int[] { -1, 0, 1, 0, -1 };
  public static int swimInWater(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    int[][] distance = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        distance[i][j] = Integer.MAX_VALUE;
      }
    }
    distance[0][0] = grid[0][0];
    boolean[][] visited = new boolean[n][m];
    // 0 : 格子的行
    // 1 : 格子的列
    // 2 : 源点到当前格子的代价
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    heap.add(new int[] { 0, 0, grid[0][0] });
    while (!heap.isEmpty()) {
      int x = heap.peek()[0];
      int y = heap.peek()[1];
      int c = heap.peek()[2];
      heap.poll();
      if (visited[x][y]) {
        continue;
      }
      visited[x][y] = true;
      if (x == n - 1 && y == m - 1) {
        // 常见剪枝
        // 发现终点直接返回
        // 不用等都结束
        return c;
      }
      for (int i = 0, nx, ny, nc; i < 4; i++) {
        nx = x + move[i];
        ny = y + move[i + 1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
          nc = Math.max(c, grid[nx][ny]);
          if (nc < distance[nx][ny]) {
            distance[nx][ny] = nc;
            heap.add(new int[] { nx, ny, nc });
          }
        }
      }
    }
    return -1;
  }
}

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

// 获取所有钥匙的最短路径

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

// ‘.’ 代表一个空房间、‘#’ 代表一堵、‘@’ 是起点

// 小写字母代表钥匙、大写字母代表锁

// 从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间

// 不能在网格外面行走，也无法穿过一堵墙

// 如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

// 假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，

// 字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母

// 换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁

// 另外，代表钥匙和锁的字母互为大小写并按字母顺序排列

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

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

package class064;
// 获取所有钥匙的最短路径
// 给定一个二维网格 grid ，其中：
// '.' 代表一个空房间、'#' 代表一堵、'@' 是起点
// 小写字母代表钥匙、大写字母代表锁
// 从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间
// 不能在网格外面行走，也无法穿过一堵墙
// 如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
// 假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，
// 字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
// 换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁
// 另外，代表钥匙和锁的字母互为大小写并按字母顺序排列
// 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
// 测试链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys
public class Code04_ShortestPathToGetAllKeys {
  public static int MAXN = 31;
  public static int MAXM = 31;
  public static int MAXK = 6;
  // 0:上，1:右，2:下，3:左
  public static int[] move = new int[] { -1, 0, 1, 0, -1 };
  public static char[][] grid = new char[MAXN][];
  public static boolean[][][] visited = new boolean[MAXN][MAXM][1 << MAXK];
  // 0 : 行
  // 1 : 列
  // 2 : 收集钥匙的状态
  public static int[][] queue = new int[MAXN * MAXM * (1 << MAXK)][3];
  public static int l, r, n, m, key;
  public static void build(String[] g) {
    l = r = key = 0;
    n = g.length;
    m = g[0].length();
    for (int i = 0; i < n; i++) {
      grid[i] = g[i].toCharArray();
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (grid[i][j] == '@') {
          queue[r][0] = i;
          queue[r][1] = j;
          // 0 : 000000
          queue[r++][2] = 0;
        }
        if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
          key |= 1 << (grid[i][j] - 'a');
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        for (int s = 0; s <= key; s++) {
          visited[i][j][s] = false;
        }
      }
    }
  }
  public static int shortestPathAllKeys(String[] g) {
    build(g);
    int level = 1;
    while (l < r) {
      for (int k = 0, size = r - l, x, y, s; k < size; k++) {
        x = queue[l][0];
        y = queue[l][1];
        s = queue[l++][2];
        for (int i = 0, nx, ny, ns; i < 4; i++) {
          nx = x + move[i];
          ny = y + move[i + 1];
          ns = s;
          if (nx < 0 || nx == n || ny < 0 || ny == m || grid[nx][ny] == '#') {
            // 越界或者障碍
            continue;
          }
          if (grid[nx][ny] >= 'A' && grid[nx][ny] <= 'F' && ((ns & (1 << (grid[nx][ny] - 'A'))) == 0)) {
            // 是锁，又没有对应的钥匙
            continue;
          }
          if (grid[nx][ny] >= 'a' && grid[nx][ny] <= 'f') {
            // 是某一把钥匙
            ns |= (1 << (grid[nx][ny] - 'a'));
          }
          if (ns == key) {
            // 常见剪枝
            // 发现终点直接返回
            // 不用等都结束
            return level;
          }
          if (!visited[nx][ny][ns]) {
            visited[nx][ny][ns] = true;
            queue[r][0] = nx;
            queue[r][1] = ny;
            queue[r++][2] = ns;
          }
        }
      }
      level++;
    }
    return -1;
  }
}

code5 LCP 35. 电动车游城市

// 电动车游城市

// 小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间

// 小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1

// 他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，

// 表示城市 A、B 间存在双向通路。

// 初始状态，电动车电量为 0。每个城市都设有充电桩，

// charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。

// 请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end

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

package class064;
import java.util.ArrayList;
import java.util.PriorityQueue;
// 电动车游城市
// 小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间
// 小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1
// 他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，
// 表示城市 A、B 间存在双向通路。
// 初始状态，电动车电量为 0。每个城市都设有充电桩，
// charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
// 请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end
// 测试链接 : https://leetcode.cn/problems/DFPeFJ/
public class Code05_VisitCityMinCost {
  // 电动车总电量，cnt
  public static int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
    int n = charge.length;
    ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
    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] });
    }
    // n : 0 ~ n-1，不代表图上的点
    // (点，到达这个点的电量)图上的点！
    int[][] distance = new int[n][cnt + 1];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= cnt; j++) {
        distance[i][j] = Integer.MAX_VALUE;
      }
    }
    distance[start][0] = 0;
    boolean[][] visited = new boolean[n][cnt + 1];
    // 0 : 当前点
    // 1 : 来到当前点的电量
    // 2 : 花费时间
    PriorityQueue<int[]> heap = new PriorityQueue<int[]>((a, b) -> (a[2] - b[2]));
    heap.add(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 (visited[cur][power]) {
        continue;
      }
      if (cur == end) {
        // 常见剪枝
        // 发现终点直接返回
        // 不用等都结束
        return cost;
      }
      visited[cur][power] = true;
      if (power < cnt) {
        // 充一格电
        // cur, power+1
        if (!visited[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 && !visited[nextCity][restPower] && nextCost < distance[nextCity][restPower]) {
          distance[nextCity][restPower] = nextCost;
          heap.add(new int[] { nextCity, restPower, nextCost });
        }
      }
    }
    return -1;
  }
}

code6 P4568 [JLOI2011] 飞行路线

// 飞行路线（语言提供的堆）

// Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司

// 该航空公司一共在n个城市设有业务，设这些城市分别标记为0 ~ n−1

// 一共有m种航线，每种航线连接两个城市，并且航线有一定的价格

// Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机

// 航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机

// 那么 Alice 和 Bob 这次出行最少花费多少

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

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下所有代码，把主类名改成Main，可以直接通过

code6 P4568 [JLOI2011] 飞行路线

// 飞行路线（自己手撸的堆）

// Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司

// 该航空公司一共在n个城市设有业务，设这些城市分别标记为0 ~ n−1

// 一共有m种航线，每种航线连接两个城市，并且航线有一定的价格

// Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机

// 航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机

// 那么 Alice 和 Bob 这次出行最少花费多少

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

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下所有代码，把主类名改成Main，可以直接通过

package class064;
// 飞行路线（自己手撸的堆）
// Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司
// 该航空公司一共在n个城市设有业务，设这些城市分别标记为0 ~ n−1
// 一共有m种航线，每种航线连接两个城市，并且航线有一定的价格
// Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机
// 航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机
// 那么 Alice 和 Bob 这次出行最少花费多少
// 测试链接 : https://www.luogu.com.cn/problem/P4568
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code06_FlightPath2 {
  public static int MAXN = 10001;
  public static int MAXM = 100001;
  public static int MAXK = 11;
  // 链式前向星建图需要
  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;
  // Dijkstra需要
  public static int[][] distance = new int[MAXN][MAXK];
  public static boolean[][] visited = new boolean[MAXN][MAXK];
  // 自己写的普通堆，静态结构，推荐
  // 注意是自己写的普通堆，不是反向索引堆
  // 因为(点编号，使用免费路线的次数)，两个参数的组合才是图中的点
  // 两个参数的组合对应一个点(一个堆的下标)，所以反向索引堆不好写
  // 其实也能实现，二维点变成一维下标即可
  // 但是会造成很多困惑，索性算了，就手写普通堆吧
  public static int[][] heap = new int[MAXM * MAXK][3];
  public static int heapSize;
  public static int n, m, k, s, t;
  public static void build() {
    cnt = 1;
    heapSize = 0;
    for (int i = 0; i < n; i++) {
      head[i] = 0;
      for (int j = 0; j <= k; j++) {
        distance[i][j] = Integer.MAX_VALUE;
        visited[i][j] = false;
      }
    }
  }
  public static void addEdge(int u, int v, int w) {
    next[cnt] = head[u];
    to[cnt] = v;
    weight[cnt] = w;
    head[u] = cnt++;
  }
  public static void push(int u, int t, int c) {
    heap[heapSize][0] = u;
    heap[heapSize][1] = t;
    heap[heapSize][2] = c;
    int i = heapSize++;
    while (heap[i][2] < heap[(i - 1) / 2][2]) {
      swap(i, (i - 1) / 2);
      i = (i - 1) / 2;
    }
  }
  public static int u, use, cost;
  public static void pop() {
    u = heap[0][0];
    use = heap[0][1];
    cost = heap[0][2];
    swap(0, --heapSize);
    heapify();
  }
  public static void heapify() {
    int i = 0;
    int l = 1;
    while (l < heapSize) {
      int best = l + 1 < heapSize && heap[l + 1][2] < heap[l][2] ? l + 1 : l;
      best = heap[best][2] < heap[i][2] ? best : i;
      if (best == i) {
        break;
      }
      swap(best, i);
      i = best;
      l = i * 2 + 1;
    }
  }
  public static void swap(int i, int j) {
    int[] tmp = heap[i];
    heap[i] = heap[j];
    heap[j] = tmp;
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken(); m = (int) in.nval;
      in.nextToken(); k = (int) in.nval;
      in.nextToken(); s = (int) in.nval;
      in.nextToken(); t = (int) in.nval;
      build();
      for (int i = 0, a, b, c; i < m; i++) {
        in.nextToken(); a = (int) in.nval;
        in.nextToken(); b = (int) in.nval;
        in.nextToken(); c = (int) in.nval;
        addEdge(a, b, c);
        addEdge(b, a, c);
      }
      out.println(dijkstra());
    }
    out.flush();
    out.close();
    br.close();
  }
  public static int dijkstra() {
    distance[s][0] = 0;
    push(s, 0, 0);
    while (heapSize > 0) {
      pop();
      if (visited[u][use]) {
        continue;
      }
      visited[u][use] = true;
      if (u == t) {
        // 常见剪枝
        // 发现终点直接返回
        // 不用等都结束
        return cost;
      }
      for (int ei = head[u], v, w; ei > 0; ei = next[ei]) {
        v = to[ei];
        w = weight[ei];
        if (use < k && distance[v][use + 1] > distance[u][use]) {
          // 使用免费
          distance[v][use + 1] = distance[u][use];
          push(v, use + 1, distance[v][use + 1]);
        }
        if (distance[v][use] > distance[u][use] + w) {
          // 不用免费
          distance[v][use] = distance[u][use] + w;
          push(v, use, distance[v][use]);
        }
      }
    }
    return -1;
  }
}

2023-12-9 19:21:42

文章标签：
算法
索引
定位技术
关键词：
算法dijkstra
dijkstra算法
算法短路
算法最短路
dijkstra算法短路
日星月云
目录
相关文章
java冯坚持
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
70 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
aliyun1792367740-35101
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法（C/C++)
迪杰斯特拉(Dijkstra)算法（C/C++)
aliyun1792367740-35101
81 0
热爱技术的小郑
|
3月前
|
机器学习/深度学习 算法 Java
算法设计（动态规划应用实验报告）实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法，包括它们的伪代码描述、Java源代码实现、时间效率分析，并展示了算法的测试用例结果，使读者对贪婪技术及其应用有了更深入的理解。
热爱技术的小郑
65 0
算法设计（动态规划应用实验报告）实现基于贪婪技术思想的Prim算法、Dijkstra算法
VipSoft
|
3月前
|
算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
VipSoft
66 0
软件算法开发
|
4月前
|
算法
基于Dijkstra算法的最优行驶路线搜索matlab仿真,以实际城市复杂路线为例进行测试
使用MATLAB2022a实现的Dijkstra算法在城市地图上搜索最优行驶路线的仿真。用户通过鼠标点击设定起点和终点，算法规划路径并显示长度。测试显示，尽管在某些复杂情况下计算路径可能与实际有偏差，但多数场景下Dijkstra算法能找到接近最短路径。核心代码包括图的显示、用户交互及Dijkstra算法实现。算法基于图论，不断更新未访问节点的最短路径。测试结果证明其在简单路线及多数复杂城市路况下表现良好，但在交通拥堵等特殊情况下需结合其他数据提升准确性。
软件算法开发
111 0
百锦再@新空间代码工作室
|
4月前
|
资源调度 算法 定位技术
算法——Dijkstra算法
算法——Dijkstra算法
百锦再@新空间代码工作室
66 1
数据结构和算法编程
|
4月前
|
算法 Java C++
《经典图论算法》迪杰斯特拉算法(Dijkstra)
这个是求最短路径的迪杰斯特拉算法，另外我还写了50多种《经典图论算法》，每种都使用C++和Java两种语言实现，熟练掌握之后无论是参加蓝桥杯，信奥赛，还是其他比赛，或者是面试，都能轻松应对。
数据结构和算法编程
65 0
简简单单做算法
|
28天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中，通过游戏理论优化动态频谱访问，提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本：Matlab 2022a。完整代码包含详细中文注释和操作视频。
简简单单做算法
40 2
简简单单做算法
|
13天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值（FCM）算法的图像分割技术。算法运行效果良好，无水印。使用MATLAB 2022a开发，提供完整代码及中文注释，附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割，适用于灰度和彩色图像，广泛应用于医学影像、遥感图像等领域。
简简单单做算法
49 9
软件算法开发
|
14天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题（JSSP）通过遗传算法（GA）和模拟退火算法（SA）优化多个作业在并行工作中心上的加工顺序和时间，以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试，展示了有效性和可行性。核心程序采用作业列表表示法，结合遗传操作和模拟退火过程，提高算法性能。
软件算法开发
44 9

热门文章

最新文章

  • 1
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 2
    算法学习之顺序结构
  • 3
    泛型KMP算法
  • 4
    OneMob（一体传媒）：大数据算法 让营销更精准
  • 5
    【算法】算法之美—Fire Net
  • 6
    Node.js使用jsrsasign实现SHA256withRSA加密算法
  • 7
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 8
    字符串相似度算法 递归与动态规划求解分析
  • 9
    【算法研究】Bresenham画线算法
  • 10
    算法导论第十四章 数据结构的扩张
  • 1
    算法：位运算
    38
  • 2
    算法：双指针
    52
  • 3
    基于harris角点和RANSAC算法的图像拼接matlab仿真
    91
  • 4
    m基于遗传优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
    76
  • 5
    深入浅出JVM（十三）之垃圾回收算法细节
    53
  • 6
    深入浅出JVM（十二）之垃圾回收算法
    44
  • 7
    常见的算法排序（2）
    46
  • 8
    数据结构与算法 动态规划(启发式搜索、遗传算法、强化学习待完善)
    99
  • 9
    数据结构与算法 回溯
    36
  • 10
    数据结构与算法 分治
    39

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    阿里云OSS设置跨域访问