DijkstraDetresse

/**
 * Using this template, your task is to implement functions denoted by TODO in the comments.
 *
 * In this task, you work with a directed weighted graph. Your task is to find the shortest
 * path from u to all vertices of the graph using Dijkstra's algorithm.
 *
 * You can define new classes and methods and extend the existing. Just do not change the API.
 *
 * Find the detailed description by the methods of class Graph.
 *
 * The Java project also contains tests, in Eclipse you can run them by left-clicking:
 * test/(default package)/JUnitTest.java and selecting Run as -> JUnitTest.java.
 *
 * The tests will show you if they passed/failed. In case of fail, you can see an exception
 * if the code did not finished, or the difference between your output and expected output.
 * The test names should help you to explain what is being tested. You can also see the content
 * of the tests, for the format of the input, see <code>read</code> method.
 *
 * The output format is described in the comment of <code>output</code> method.
 */

/**
 * This imports policy applies to all programming assignments and the exam.
 *
 * You are forbidden to add any other import statements. Make sure that you do not leave any
 * imports commented out, or that your IDE does not add any automatically. You can recognize
 * allowed imports by the <code>// allowed import</code> comment.
 * Calls by the fully qualified name are treated as imports as well. Those are, for example,
 * <code>java.util.Arrays.sort</code>, or <code>java.util.Arrays.binarySearch</code>.
 * You can use data structures we provide to you by imports, by our definitions (even
 * implicitly used classes of packages, such as methods of Object those are inherited with
 * every class declaration, Array, or String), or data structures that you write on your own.
 * Usage of common arrays (<code>type[] variable</code>) is not restricted.
 *
 * Note that Judge is not enforcing this policy. So if you violate this policy, you may lose the
 * bonus points even if Judge accepts your submission.
 *
 * The general exceptions out of this policy is the package Math. The exceptions that are specific
 * to a given template are written down by its imports.
 */
// you can import both java.util.Comparator as well as java.lang.Comparable for this task
// import java.util.PriorityQueue; // allowed import
import java.util.StringTokenizer; // allowed import
import java.io.BufferedReader; // allowed import
import java.io.IOException; // allowed import
import java.io.InputStream; // allowed import
import java.io.InputStreamReader; // allowed import
import java.io.PrintStream; // allowed import
import java.lang.Math; // allowed import

class Main {
    public static void main(String[] args) {
        ReadAndWrite rw = new ReadAndWrite();
        rw.readAndSolve(System.in, System.out);
    }
}

class PQPairs implements Comparable<PQPairs> {
    int vertex;
    int distance;

    public PQPairs(int v, int d) {
        vertex = v;
        distance = d;
    }

    @Override
    public int compareTo(PQPairs other) {
        if(this.distance > other.distance) {
            return 1;
        } else if (this.distance < other.distance) {
            return -1;
        } else {
            return 0;
        }
    }
}

class Graph {
    int[][] matrix; // directed graph represented by a distance matrix
    // if you need, you can store other attributes
    // for each graph, method <code>dijkstra</code> is called just once

    /**
     * The class is instantiated once for every graph.
     *
     * Each graph contains 0 on the diagonal (distance u to u is 0)
     * and <code>Integer.MAX_VALUE</code> states for a missing edge.
     *
     * All edge lengths are positive.
     */
    Graph(int n) {
        matrix = new int[n][n];

        for(int i = 0; i < n; i++){
            for(int  j = 0; j < n; j++){
                if(i == j){
                    matrix[i][j] = 0;
                }else{
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
    }

    /**
     * Inserts an edge from u to v with given weight.
     */
    public void addEdge(int u, int v, int weight){
         if((u < 0 || u >= matrix.length) || (v < 0 || v >= matrix.length)) {
             return;
         }
         matrix[u][v] = weight;
    }

   /**
    * TODO: Return an array of the shortest paths from vertex
    * <code>from</code> to all vertices. That means that the
    * the returned array will on position [i] contain distance
    * from <code>from</code> to i.
    *
    * If some vertex is not reachable, return <code>Integer.MAX_VALUE</code>
    * for that vertex.
    */
    int[] dijkstra(int from) {
        PriorityQueue pq = new PriorityQueue(matrix.length);
        pq.insert(new Vertex(from, 0));
        int[] distances = new int[matrix.length];
        for (int i = 0; i < distances.length; i++) {
            if (i == from) distances[i] = 0;
            else distances[i] = Integer.MAX_VALUE;
        }
        boolean[] processed = new boolean[matrix.length];
        boolean[] discovered = new boolean[matrix.length];
        discovered[0] = true;


        while (!pq.isEmpty()) {

            Vertex u = pq.extractMin();

            if (processed[u.id]) {
                continue;
            }

            processed[u.id] = true;
            distances[u.id] = u.distance;

            for(int v = 0; v < matrix.length; v++) {

                if (matrix[u.id][v] != Integer.MAX_VALUE && !processed[v]) {

                    if (distances[v] == Integer.MAX_VALUE) {
                        Vertex newVertex = new Vertex(v, distances[u.id] + matrix[u.id][v]);
                        distances[v] = newVertex.distance;
                        pq.insert(newVertex);

                    }
                    if (distances[v] > distances[u.id] + matrix[u.id][v]) {
                        distances[v] = distances[u.id] + matrix[u.id][v];
                        pq.decreaseKey(v, distances[v]);
                    }
                }
            }
        }


        return distances;
    }


}

class Vertex {
    int distance;
    int id;

    public Vertex(int id, int v) {
        this.distance = v;
        this.id = id;
    }
}

class PriorityQueue {
    Vertex[] keys;
    int[] pointer;
    int N;
    int n;

    public PriorityQueue(int N) {
        this.keys = new Vertex[N];
        this.pointer = new int[N];
        this.N = N;
        this.n = 0;
    }

    public void insert(Vertex v) {
        if (n < N) {
            keys[n++] = v;
            pointer[v.id] = n - 1;
            siftUp(n - 1);
        }
    }

    public Vertex extractMin() {
        Vertex result = keys[0];

        swap(0, --n);
        //keys[n] = null;
        //pointer[result.id] = -1;
        siftDown(0);

        return result;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public void decreaseKey(int id, int newDistance) {
        keys[pointer[id]].distance = newDistance;
        siftUp(pointer[id]);
    }

    public void siftDown(int index) {
        while (leftIndex(index) < n) {
            int j = leftIndex(index);

            if (j + 1 < n)
                if (keys[j].distance > keys[j + 1].distance)
                    j = j+1;

            if (keys[index].distance < keys[j].distance) break;

            swap(index, j);
            index = j;
        }
    }

    public void siftUp(int index) {
        while (parentIndex(index) >= 0 && keys[parentIndex(index)].distance > keys[index].distance) {
            swap(index, parentIndex(index));
            index = parentIndex(index);
        }
    }

    public int parentIndex(int index) {
        return (index + 1) / 2 - 1;
    }

    public int leftIndex(int index) {
        return 2*(index + 1) - 1;
    }

    public int rightIndex(int index) {
        return 2*(index + 1);
    }

    public void swap(int i, int j) {
        Vertex tmpA = keys[i];
        int tmpB = pointer[i];
        keys[i] = keys[j];
        pointer[i] = pointer[j];
        keys[j] = tmpA;
        pointer[j] = tmpB;
    }
}


///////////////////////////////////////////////////////////////////////
// DO NOT MODIFY THE FOLLOWING CODE, YOU CAN COMPLETELY IGNORE IT
// WE MAY USE LANGUAGE CONSTRUCTS THAT YOU MAY HAVE NOT SEEN SO FAR
///////////////////////////////////////////////////////////////////////

class ReadAndWrite {
    /**
     * Parses input of n distance matrices
     */
    void readAndSolve(InputStream in, PrintStream out) {
        FastReader s = new FastReader(in);

        int n = s.nextInt();

        for (int i = 0; i < n; i++) {
            int vertices = s.nextInt();

            Graph g = new Graph(vertices);

            int w;
            for (int u = 0; u < vertices; u++) {
                for (int v = 0; v < vertices; v++) {
                    w = s.nextInt();
                    if (w != -1) {
                        g.addEdge(u, v, w);
                    }
                }
            }

            out.println(java.util.Arrays.toString(g.dijkstra(0)));
        }
    }
}

/**
 * Ignore this class please. It is used for input parsing. Source:
 * https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
 */
class FastReader {
    BufferedReader br;
    StringTokenizer st;

    FastReader(InputStream in) {
        br = new BufferedReader(new InputStreamReader(in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    char nextChar() {
        return next().charAt(0);
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}