题目描述
blablabla
样例
import java.util.*;
class Main{
static int[] h, ne, e, w;
static int idx;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
init(n, m);
for (int i = 0; i < m; i++) {
int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
addEdge(a, b, c);
}
System.out.println(dijkstra(n));
}
public static void init(int n, int m) {
h = new int[n + 1];
Arrays.fill(h, -1);
ne = new int[m];
e = new int[m];
w = new int[m];
idx = 0;
}
public static void addEdge(int a, int b, int c) {
ne[idx] = h[a];
h[a] = idx;
e[idx] = b;
w[idx] = c;
idx++;
}
public static int dijkstra(int n) {
int[] dis = new int[n + 1];
dis[1] = 0;
Arrays.fill(dis, 0x3f3f3f3f);
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
queue.offer(new int[]{1, 0});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int curNode = cur[0], curDis = cur[1];
if (curNode == n) return curDis;
for (int nextIndex = h[curNode]; nextIndex != -1; nextIndex = ne[nextIndex]) {
int nextNode = e[nextIndex], weight = w[nextIndex];
if (weight + curDis < dis[nextNode]) {
dis[nextNode] = weight + curDis;
queue.offer(new int[]{nextNode, dis[nextNode]});
}
}
}
return -1;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla