hackerrank：与Dijkstra算法有关的问题超出了时间限制

Question

我目前正在针对hackerrank练习图形问题，并针对以下两个问题：Dijkstra: Shortest Reach 2和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;


}

杰克的代码会被提起

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]);
    }



}

Answer 1

您可以使用以下代码解决此问题：

Dijkstra：最短覆盖面2]的解决方案>

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

class Pair implements Comparable<Pair> {

  public int x;
  public int c;

  Pair(int x, int c) {
    this.x = x;
    this.c = c;
  }

  public int compareTo(Pair b) {
    return (b.c < this.c) ? 1 : -1;
  }
}


public class Solution {

  public static ArrayList<HashMap<Integer, Integer>> adj;
  public static int[] shortestPaths;

  public static void dijkstra(int s) {
    shortestPaths = new int[adj.size()];
    for (int i = 0; i < adj.size(); i++) {
      shortestPaths[i] = Integer.MAX_VALUE;
    }
    shortestPaths[s] = 0;
    boolean[] visited = new boolean[adj.size()];
    PriorityQueue<Pair> queue = new PriorityQueue<>();
    queue.add(new Pair(s, 0));

    while (!queue.isEmpty()) {
      Pair current = queue.poll();
      if (!visited[current.x]) {
        visited[current.x] = true;
        Iterator<Map.Entry<Integer, Integer>> entries = adj.get(current.x).entrySet().iterator();

        while (entries.hasNext()) {
          Map.Entry<Integer, Integer> entry = entries.next();
          if (current.c + entry.getValue() < shortestPaths[entry.getKey()]) {
            shortestPaths[entry.getKey()] = current.c + entry.getValue();
            if (!visited[entry.getKey()]) {
              queue.add(new Pair(entry.getKey(), shortestPaths[entry.getKey()]));
            }
          }
        }
      }
    }
  }

  public static void main(String[] args) {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    try {
      int t = Integer.parseInt(in.readLine());
      for (int i = 0; i < t; i++) {
        String[] stmp = in.readLine().split(" ");
        int n = Integer.parseInt(stmp[0]);
        int m = Integer.parseInt(stmp[1]);

        adj = new ArrayList<HashMap<Integer, Integer>>();
        for (int j = 0; j < n; j++) {
          adj.add(new HashMap<>());
        }

        for (int j = 0; j < m; j++) {
          stmp = in.readLine().split(" ");
          int x = Integer.parseInt(stmp[0]);
          int y = Integer.parseInt(stmp[1]);
          int r = Integer.parseInt(stmp[2]);
          x--;
          y--;

          if (!adj.get(x).containsKey(y) || adj.get(x).get(y) > r) {
            adj.get(x).put(y, r);
          }
          if (!adj.get(y).containsKey(x) || adj.get(y).get(x) > r) {
            adj.get(y).put(x, r);
          }
        }

        int s = Integer.parseInt(in.readLine());
        s--;
        dijkstra(s);
        StringBuilder out = new StringBuilder("");
        for (int j = 0; j < n; j++) {
          if (s != j) {
            if (shortestPaths[j] == Integer.MAX_VALUE) {
              out.append("-1 ");
            } else {
              out.append(shortestPaths[j]);
              out.append(" ");
            }
          }
        }
        out.append("\n");
        System.out.print(out.toString());
      }
    } catch (Exception e) {
    }
  }
}
解决方案[[杰克被提

import java.io.*;
import java.util.*;

public class Solution {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //Get number of stations
    String[] line = br.readLine().split(" ");
    final int N = Integer.parseInt(line[0]);

    //Initialize "stations":
    //  In this case this is just a list of connecting stations
    //  and there's no need for a Station class/structure, since
    //  the station id can be represented by the stations index
    //  and the connecting stations by the list in that index.
    final List<List<Connection>> stations = new ArrayList<List<Connection>>(N);
    for(int i = 0; i++ < N; stations.add(new ArrayList<Connection>())){}

    //Get connections and their fares
    for(int E = Integer.parseInt(line[1]); E > 0; --E){
      line = br.readLine().split(" ");
      final int A = Integer.parseInt(line[0]) - 1;
      final int B = Integer.parseInt(line[1]) - 1;
      final int C = Integer.parseInt(line[2]);
      final Connection connection = new Connection(A, B, C);
      stations.get(A).add(connection);
      stations.get(B).add(connection);
    }

    //GC: Remove input reader
    br.close();
    br = null;

    //Get lowest fare from stations 1 to N
    final int minFare = getMinFare(stations, 0, N-1);
    System.out.println((minFare < 0) ? "NO PATH EXISTS" : minFare);
  }

  private static int getMinFare(final List<List<Connection>> stations, final int origin, final int destination){

    //Initialize min fares to max fare
    final int N = stations.size();
    final int[] minFares = new int[N];
    for(int i = 0, c = Integer.MAX_VALUE; i < N; minFares[i++] = c){}

    //Starting at origin, travel each route in min fare order until destination reached
    final Queue<Pair<Integer, Integer>> q = new PriorityQueue<Pair<Integer, Integer>>(N);
    minFares[origin] = 0;
    q.add(new Pair<Integer, Integer>(origin, 0));
    do {

      //Get current station and min fare
      final int stationId = q.poll().key;
      final int curFare = minFares[stationId];

      //If destination reached
      if(stationId == destination){
        return curFare;
      }

      //Visit connecting stations that are unvisited / could be visited cheaper
      for(Connection connection : stations.get(stationId)){
        final int connectingStationId = connection.getStationId(stationId);
        final int minFare = minFares[connectingStationId];
        final int newMinFare = Math.max(curFare, connection.fare);
        if(minFare > newMinFare){
          minFares[connectingStationId] = newMinFare;
          q.add(new Pair<Integer, Integer>(connectingStationId, newMinFare));
        }
      }
    } while (!q.isEmpty());

    //If destination is unreachable
    return -1;
  }

  private static class Pair<K, V extends Comparable<V>> implements Comparable<Pair<K, V>>{
    public final K key;
    public final V value;

    public Pair(final K key, final V value){
      this.key = key;
      this.value = value;
    }

    public int compareTo(Pair<K, V> b){
      return this.value.compareTo(b.value);
    }
  }

  private static class Connection {
    public final int fare;
    public final int stationIds;

    public Connection(final int stationId1, final int stationId2, final int fare){
      this.fare = fare;
      this.stationIds = stationId1 ^ stationId2;
    }

    public int getStationId(final int stationId){
      return stationIds ^ stationId;
    }
  }
}

我希望它能解决您的问题