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 : 000000queue[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 {// 電動車總電量，cntpublic 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+1if (!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;}}