\color{Red}{热浪——单源最短路}
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
解析
最简单的模板题,具体细节可以看我对应的题解
我的SPFA全题解
我的Dijkstra全题解
Dijkstra 优先队列优化
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
static int n, m, S, E, idx, N = 6200, M = 2 * N + 10;
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] h = new int[N];
static int[] w = new int[M];
static int[] d = new int[N];
static boolean[] st = new boolean[N];
static void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
static class Node {
int dist, num;
public Node(int dist, int num) {
this.dist = dist;
this.num = num;
}
}
static void dijkstra() {
PriorityQueue<Node> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.dist));
heap.add(new Node(0, S));
d[S] = 0;
while (!heap.isEmpty()) {
Node node = heap.poll();
int num = node.num;
int dist = node.dist;
if (st[num]) continue;
st[num] = true;
for (int i = h[num]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] > dist + w[i]) {
d[j] = dist + w[i];
if (!st[j]) heap.add(new Node(d[j], j));
}
}
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
Arrays.fill(h, -1);
Arrays.fill(d, 0x3f3f3f3f);
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
S = Integer.parseInt(s1[2]);
E = Integer.parseInt(s1[3]);
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(a, b, c);
add(b, a, c);
}
dijkstra();
System.out.println(d[E]);
}
}
SPFA 循环队列
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int n, m, S, E, idx, N = 6200, M = 2 * N + 10;
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] h = new int[N];
static int[] w = new int[M];
static int[] d = new int[N];
static boolean[] st = new boolean[N];
static void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
static void spfa() {
int[] q = new int[N];
d[S] = 0;
st[S] = true;
int hh = 0, tt = 1;
q[hh] = S;
while (hh != tt){
int num = q[hh++];
if (hh == N) hh = 0;
st[num] = false;
for (int i = h[num]; i != -1; i=ne[i]) {
int j = e[i];
if (d[j] > d[num] + w[i]){
d[j] = d[num] + w[i];
if (!st[j]){
st[j] = true;
q[tt++] = j;
if (tt == N) tt = 0;
}
}
}
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
Arrays.fill(h, -1);
Arrays.fill(d, 0x3f3f3f3f);
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
S = Integer.parseInt(s1[2]);
E = Integer.parseInt(s1[3]);
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(a, b, c);
add(b, a, c);
}
spfa();
System.out.println(d[E]);
}
}