LeetCode 743 Network Delay Time(SPFAまたはDijkstra)

There are  N  network nodes, labelled  1  to  N .
Given  times , a list of travel times as directededges  times[i] = (u, v, w) , where  u  is the source node,  v  is the target node, and  w  is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node  K . How long will it take for all nodes to receive the signal? If it is impossible, return  -1 .
Example 1:
 

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

N  will be in the range  [1, 100] .

K  will be in the range  [1, N] .

The length of  times  will be in the range  [1, 6000] .

All edges  times[i] = (u, v, w)  will have  1 <= u, v <= N  and  0 <= w <= 100 .

裸の最短の問題、spfaを書き慣れたため、運行時間は理想的ではありませんて、原因はこの問題のデータが比較的に特殊で、点数は最大でやっと100で、必然的に稠密な図であることを想像することができて、道理でDijkstraに行くべきで、spfaは比較的にまばらな図に適しています
19 ms、時間83.22%を破った

class Solution {
    
    class Edge {
        int to, w;
        public Edge(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }

    public HashMap> mp;
    public int[] dist = new int[101];
    public boolean[] vis = new boolean[101];

    public void SPFA(HashMap> mp, int K) {
        Queue q = new LinkedList<>();
        dist[K] = 0;
        vis[K] = true;
        q.offer(K);
        while (q.size() > 0) {
            int cur = q.poll();
            vis[cur] = false;
            if (!mp.containsKey(cur)) {
                continue;
            }
            for (int i = 0; i < mp.get(cur).size(); i++) {
                Edge e = mp.get(cur).get(i);
                if (dist[e.to] == -1 || dist[e.to] > dist[cur] + e.w) {
                    dist[e.to] = dist[cur] + e.w;
                    if (!vis[e.to]) {
                        vis[e.to] = true;
                        q.offer(e.to);
                    } 
                }
            }
        }
    }
    
    public int networkDelayTime(int[][] times, int N, int K) {
        mp = new HashMap<>();
        for (int i = 0; i < times.length; i++) {
            if (!mp.containsKey(times[i][0])) {
                mp.put(times[i][0], new ArrayList());
            }
            mp.get(times[i][0]).add(new Edge(times[i][1], times[i][2]));
        }
        Arrays.fill(dist, -1);
        SPFA(mp, K);
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] == -1) {
                return -1;
            }
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
}