LeetCode：2642. 设计可以求最短路径的图类（SPFA Java）

2642. 设计可以求最短路径的图类

题目描述：

实现代码与解析：

SPFA

原理思路：

2642. 设计可以求最短路径的图类

题目描述：

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。

请你实现一个 Graph 类：

Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost] 。数据保证添加这条边之前对应的两个节点之间没有有向边。
int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径最小代价。如果路径不存在，返回 -1 。一条路径的代价是路径中所有边代价之和。

示例 1：

输入：
["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
输出：
[null, 6, -1, null, 6]

解释：
Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
g.shortestPath(3, 2); // 返回 6 。从 3 到 2 的最短路径如第一幅图所示：3 -> 0 -> 1 -> 2 ，总代价为 3 + 2 + 1 = 6 。
g.shortestPath(0, 3); // 返回 -1 。没有从 0 到 3 的路径。
g.addEdge([1, 3, 4]); // 添加一条节点 1 到节点 3 的边，得到第二幅图。
g.shortestPath(0, 3); // 返回 6 。从 0 到 3 的最短路径为 0 -> 1 -> 3 ，总代价为 2 + 4 = 6 。

提示：

1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= fromi, toi, from, to, node1, node2 <= n - 1
1 <= edgeCosti, edgeCost <= 106
图中任何时候都不会有重边和自环。
调用 addEdge 至多 100 次。
调用 shortestPath 至多 100 次。

实现代码与解析：

SPFA

class Graph {
    final int N = 210;

    int[] h = new int[N], e = new int[N * N], ne = new int[N * N], w = new int[N * N];
    int[] dist = new int[N];
    int idx;
    boolean[] st = new boolean[N];

    public void add(int a, int b, int c) {
        w[idx] = c; e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
    }

    public Graph(int n, int[][] edges) {
        Arrays.fill(h, -1);
        for (int[] e: edges) {
            int a = e[0];
            int b = e[1];
            int c = e[2];
            add(a, b, c);
        }
    }

    public void addEdge(int[] edge) {
        add(edge[0], edge[1], edge[2]);
    }

    public int shortestPath(int node1, int node2) {
        if (node1 == node2) return 0; // 处理起点就是终点的情况

        Arrays.fill(dist, 0x3f3f3f3f); // 每次都要初始化
        Arrays.fill(st, false);// 每次都要初始化
        Queue<Integer> q = new LinkedList<>();
        q.offer(node1);
        st[node1] = true;
        dist[node1] = 0;
        while (!q.isEmpty()) {
            int t = q.peek();
            q.poll();
            st[t] = false;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[t] + w[i] <= dist[j]) {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) {
                        st[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
        return dist[node2] ==  0x3f3f3f3f ? -1 : dist[node2];
    }
}