java - hackerrank：与 Dijkstra 算法相关的问题超过了时间限制

Question

我目前正在练习关于hackerrank的图形问题以及这两个问题： Dijkstra: Shortest Reach 2 and enter link description here。我在这两个问题上都使用了 Dijkstra，并且通过了大部分测试用例，并且有 1 或 2 个用例表示超过了时间限制。我在这里粘贴我的代码，希望任何人都可以提供一些建议。谢谢。

Dijkstra 的代码：最短距离 2

static class Pair {
    int p;
    int dis;
    public Pair(int p, int dis) {
        this.p = p;
        this.dis = dis;
    }
}

// Complete the shortestReach function below.
static int[] shortestReach(int n, int[][] edges, int s) {
    Map < Integer, List < Pair >> map = new HashMap < > ();
    for (int[] edge: edges) {
        map.computeIfAbsent(edge[0], k - > new ArrayList < > ()).add(new Pair(edge[1], edge[2]));
        map.computeIfAbsent(edge[1], k - > new ArrayList < > ()).add(new Pair(edge[0], edge[2]));
    }
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[s] = 0;
    boolean[] visited = new boolean[n + 1];
    PriorityQueue < Integer > pq = new PriorityQueue < > ((a, b) - > (dist[a] - dist[b]));
    pq.add(s);
    while (!pq.isEmpty()) {
        int cur = pq.poll();
        if (visited[cur]) continue;
        visited[cur] = true;
        if (map.containsKey(cur)) {
            for (Pair neighbor: map.get(cur)) {
                //if(visited[neighbor.p]) continue;
                if (dist[cur] + neighbor.dis < dist[neighbor.p]) {
                    dist[neighbor.p] = dist[cur] + neighbor.dis;
                    if (!visited[neighbor.p] && pq.contains(neighbor.p)) {
                        pq.remove(neighbor.p);
                        pq.add(neighbor.p);
                    } else if (!visited[neighbor.p]) {
                        pq.add(neighbor.p);
                    }
                }
            }
        }
    }
    int[] res = new int[n - 1];
    int p = 0;
    for (int i = 1; i <= n; i++) {
        if (i == s) continue;
        res[p++] = dist[i] == Integer.MAX_VALUE ? -1 : dist[i];
    }
    return res;


}

Jack 的代码去 Rapture

static class Edge {
    int next;
    int dis;
    public Edge(int next, int dis) {
        this.next = next;
        this.dis = dis;
    }
}

public static void getCost(int gNodes, int gEdges, List < Integer > gFrom, List < Integer > gTo, List < Integer > gWeight) {

    Map < Integer, List < Edge >> routes = new HashMap < > ();
    for (int i = 0; i < gEdges; i++) {
        routes.computeIfAbsent(gFrom.get(i), k - > new ArrayList < > ()).add(new Edge(gTo.get(i), gWeight.get(i)));
        routes.computeIfAbsent(gTo.get(i), k - > new ArrayList < > ()).add(new Edge(gFrom.get(i), gWeight.get(i)));
    }
    int[] dist = new int[gNodes + 1];
    boolean[] visited = new boolean[gNodes + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[1] = 0;
    PriorityQueue < Integer > pq = new PriorityQueue < > ((a, b) - > (dist[a] - dist[b]));

    pq.add(1);
    while (!pq.isEmpty()) {
        int cur = pq.poll();
        if (visited[cur]) continue;
        visited[cur] = true;
        if (routes.containsKey(cur)) {
            for (Edge e: routes.get(cur)) {
                if (Math.max(dist[cur], e.dis) < dist[e.next]) {
                    dist[e.next] = Math.max(dist[cur], e.dis);
                    if (!visited[e.next] && pq.contains(e.next)) {
                        pq.remove(e.next);
                        pq.add(e.next);
                    } else if (!visited[e.next]) {
                        pq.add(e.next);
                    }
                }
            }
        }
    }
    if (dist[gNodes] == Integer.MAX_VALUE) {
        System.out.println("NO PATH EXISTS");
    } else {
        System.out.println(dist[gNodes]);
    }



}

标签： javaalgorithmgraphdijkstra