Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.6 kB
3
Indexable
public static List<Integer> shortestReach(int n, List<List<Integer>> edges, int s) {
        // Write your code here
        ArrayList<ArrayList<Edge>> graph = new ArrayList<>();

        int[] length = new int[n + 1];
        Arrays.fill(length, -1);
        length[s] = 0;

        boolean[] visited = new boolean[n + 1];
        Arrays.fill(visited, false);
        visited[s] = true;

        for (int i = 0;i <= n;i++) {
            graph.add(new ArrayList<Edge>());
        }

        for (int i = 0;i < edges.size();i++) {
            int vertice1 = edges.get(i).get(0), vertice2 = edges.get(i).get(1), weight = edges.get(i).get(2);
            graph.get(vertice1).add(new Edge(vertice1, vertice2, weight));
            graph.get(vertice2).add(new Edge(vertice2, vertice1, weight));
        }

        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(s);
        Hashtable<Integer, Integer> minNode = new Hashtable<Integer, Integer>((int) (n * 0.75));
        Integer minNodeIndex = null;

        while (!queue.isEmpty()) {
            int vertice = queue.removeFirst();
            //minNode.remove(vertice);
            minNodeIndex = null;
            visited[vertice] = true;
            for (Edge edge : graph.get(vertice)) {
                if (!visited[edge.vertice2]) {
                    if (length[edge.vertice2] == -1) {
                        length[edge.vertice2] = length[vertice] + edge.weight;
                    } else {
                        length[edge.vertice2] = Math.min(length[vertice] + edge.weight, length[edge.vertice2]);
                    }
                    if (length[edge.vertice2] < (minNode.get(edge.vertice2) == null ? length[edge.vertice2] + 1 : minNode.get(edge.vertice2))) {
                        minNode.put(edge.vertice2, length[edge.vertice2]);
                    }
                }
            }
            for (Integer key : minNode.keySet()) {
                if (visited[key]) {
                    continue;
                }
                if (minNodeIndex == null) {
                    minNodeIndex = key;
                } else {
                    if (minNode.get(minNodeIndex) > minNode.get(key)) {
                        minNodeIndex = key;
                    }
                }
            }
            if ( minNodeIndex != null) queue.add(minNodeIndex);
        }
        
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 1;i <= n;i++) {
            if (i != s) {
                result.add(length[i]);
            }
        }
        return result;
    }