题目描述
自定义堆,并实现Dijkstra求最短路 II
Java 代码
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author LSN
* @Date 2022/2/24
*/
public class Main {
static ArrayList<Line> lines[]; //邻接表
static boolean chosen[]; //标志数组
static int distance[]; //距离数组
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
chosen = new boolean[n+1];
lines = new ArrayList[n+1];
distance = new int[n+1];
for(int i=1;i<=n;i++){
lines[i] = new ArrayList<Line>();
distance[i] = 0x7fffffff;
}
//初始化堆
LSNHeap heap = new LSNHeap(distance);
for(int i=1;i<=m;i++){
int x1 = sc.nextInt();
int x2 = sc.nextInt();
int w = sc.nextInt();
Line line = new Line(x2,w);
lines[x1].add(line);
}
//初始化起点
heap.update(1,0);
//循环n轮
for(int p=1;p<=n;p++){
//从堆中得到最近点
int cur = heap.poll();
//如果不可达,无解,直接退出
if(distance[cur]==0x7fffffff) break;
//设置为已访问
chosen[cur] = true;
//用最近点更新其他点距离
int len = lines[cur].size();
for(int i = 0; i<len; i++){
Line l = lines[cur].get(i);
int np=l.np,w=l.weight;
if(distance[cur]+w<distance[np]){
heap.update(np,distance[cur]+w);
}
}
}
//如果n号点可达
if(distance[n]!=0x7fffffff) System.out.println(distance[n]);
else System.out.println(-1);
}
//边
public static class Line{
int np;
int weight;
public Line(int np,int weight){
this.np = np;
this.weight = weight;
}
}
}
//自定义堆
class LSNHeap{
private int heap[]; //堆
private int size=0; //堆大小
private int array[]; //原数组
private int ph[]; //映射关系
//构造方法:传入原数组(下标必须从1开始)
public LSNHeap(int array[]){
this.array = array;
this.heap = new int[array.length];
this.ph = new int[array.length];
this.size = array.length-1;
this.ph = new int[array.length];
for(int i=1;i<array.length;i++){
heap[i] = i;
ph[i] = i;
}
init();
}
//初始化堆
private void init(){
for(int i=size/2;i>=1;i--) down(i);
}
//交换堆中的两个元素
private void swap(int a,int b){
//先交换映射关系
int tmp = ph[heap[a]];
ph[heap[a]] = ph[heap[b]];
ph[heap[b]] = tmp;
//再交换堆的值
tmp = heap[a];
heap[a] = heap[b];
heap[b] = tmp;
}
//将堆元素上调
private void up(int u){
if(u>1 && array[heap[u]]<array[heap[u/2]]){
swap(u,u/2);
up(u/2);
}
}
//将堆元素下调
private void down(int u){
int t = u;
if(2*u<=size && array[heap[t]]>array[heap[2*u]]) t=2*u;
if(2*u+1<=size && array[heap[t]]>array[heap[2*u+1]]) t=2*u+1;
if(t!=u){
swap(t,u);
down(t);
}
}
//更新原数组中第k个元素值
public void update(int k,int x){
array[k] = x;
int hk = ph[k];
down(hk);
up(hk);
}
//获取并删除堆中的最小值
public int poll(){
int res = heap[1];
swap(1,size);
size--;
down(1);
return res;
}
}