基础版
import java.util.*;
import java.io.*;
class Main {
static int N = 150009;
static int n;
static int m;
static Map<Integer, List<Edge>> map = new HashMap<>(); // k 为某个点的编号 (1-N),v 为某个点的所有出度
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static int dijkstra() {
for (int i = 0; i < N; i++) {
dist[i] = Integer.MAX_VALUE;
st[i] = false;
}
dist[1] = 0;
Queue<Edge> queue = new PriorityQueue<Edge>((a, b) -> {
return a.w - b.w;
});
queue.add(new Edge(1, 1, 0));
while (!queue.isEmpty()) {
Edge edge = queue.poll();
if (st[edge.b]) continue;
st[edge.b] = true;
List<Edge> list = map.get(edge.b);
if (list == null || list.isEmpty()) continue;
for (Edge i : list) {
dist[i.b] = Math.min(dist[i.b], dist[i.a] + i.w);
queue.add(new Edge(1, i.b, dist[i.b]));
}
}
if (dist[n] == Integer.MAX_VALUE) return -1;
return dist[n];
}
static class Edge {
int a;
int b;
int w;
public Edge(int _a, int _b, int _w) {
a = _a;
b = _b;
w = _w;
}
}
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = r.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
for (int i = 1; i <= m; i++) {
s = r.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
int v = Integer.parseInt(s[2]);
List<Edge> list = map.getOrDefault(a, new ArrayList<Edge>());
list.add(new Edge(a, b, v));
map.put(a, list);
}
w.write(dijkstra() + " ");
r.close();
w.flush();
w.close();
}
}
预处理版
import java.util.*;
import java.io.*;
class Main {
static int n;
static int m;
static int N = 150009;
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static Map<Integer, Map<Integer, Integer>> map = new HashMap<>(); // 对于 x y z 有 x : (y:z)
static int dijkstra() {
for (int i = 0; i < N; i++) {
dist[i] = Integer.MAX_VALUE;
st[i] = false;
}
dist[1] = 0;
Queue<int[]> queue = new PriorityQueue<int[]>((a, b) -> { // 点编号,距离
return a[1] - b[1];
});
queue.add(new int[]{1, 0});
while (!queue.isEmpty()) {
int[] e = queue.poll();
if (st[e[0]]) continue;
st[e[0]] = true;
Map<Integer, Integer> mm = map.get(e[0]);
if (mm == null) continue;
for (int i : mm.keySet()) {
dist[i] = Math.min(dist[i], dist[e[0]] + mm.get(i));
queue.add(new int[]{i, dist[i]});
}
}
if (dist[n] == Integer.MAX_VALUE) return -1;
return dist[n];
}
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = r.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
for (int i = 1; i <= m; i++) {
s = r.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
if (a == b) continue; // 忽略自环
int v = Integer.parseInt(s[2]);
Map<Integer, Integer> mm = map.getOrDefault(a, new HashMap<Integer, Integer>());
if (mm.containsKey(b)){
mm.put(b, Math.min(mm.get(b), v)); // 重边只保留最小
} else {
mm.put(b, v);
}
map.put(a, mm);
}
w.write(dijkstra() + " ");
r.close();
w.flush();
w.close();
}
}