lab5_part1

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

import static java.lang.System.exit;

public class Main {

    public static void main(String[] args) {

        try {
            Scanner scanner = new Scanner(new File("./src/input.txt"));

            Integer n = scanner.nextInt();
            Integer m = scanner.nextInt();

            ArrayList<ArrayList<Pair<Integer>>> list = new ArrayList<>();
            for (Integer i = 0; i < n + 1; i++) {
                list.add(new ArrayList<>());
            }

            for (Integer i = 0; i < m; i++) {
                Integer first = scanner.nextInt();
                Integer second = scanner.nextInt();
                Integer weight = scanner.nextInt();
                list.get(first).add(new Pair<Integer>(second, weight));
            }

            Graph graph = new Graph(list);

            while (true) {
                System.out.println(" 1 - distance FROM => TO \n 2 - distances from given vertex \n 3 - Floyd \n 4 - terminate");

                Scanner consoleScanner = new Scanner(System.in);

                Integer input = consoleScanner.nextInt();

                switch (input) {
                    case 1: {
                        System.out.println("Dijkstra FROM => TO, enter two vertices: FROM, TO");
                        Integer from = consoleScanner.nextInt();
                        Integer to = consoleScanner.nextInt();

                        graph.dijkstra(from, to);
                        break;
                    }
                    case 2: {
                        System.out.println("Dijkstra from giver vertex, enter vertex");
                        Integer v = consoleScanner.nextInt();

                        graph.dijkstra2(v);
                        break;
                    }
                    case 3: {
                        System.out.println("Floyd FROM => TO + all shortest paths, enter two vertices: FROM, TO");
                        Integer from = consoleScanner.nextInt();
                        Integer to = consoleScanner.nextInt();

                        graph.floyd(from, to);
                        break;
                    }
                    case 4: {
                        exit(0);
                    }

                }
            }

        } catch (FileNotFoundException ex) {
            ex.printStackTrace();
        };
    }
}

class Graph {

    private ArrayList<ArrayList<Pair<Integer> > > graph;
    private ArrayList<Boolean> used;

    Graph(ArrayList<ArrayList<Pair<Integer> > > graph) {
        for (ArrayList<Pair<Integer>> list : graph) {
            list.sort(new Comparator<Pair<Integer>>() {
                @Override
                public int compare(Pair<Integer> int1, Pair<Integer> int2) {
                    if (int1.equals(int2)) {
                        return 0;
                    } else if (int1.first < int2.second) {
                        return -1;
                    } else {
                        return 1;
                    }
                }
            });
        }

        this.graph = graph;
    }

    /**
     * Dijkstra, FROM => TO
     * @param from
     * @param to
     */
    public void dijkstra(Integer from, Integer to) {
        Integer INF = 1000000000 + 7;
        ArrayList<Integer> dist = new ArrayList<>(Collections.nCopies(graph.size(), INF));
        dist.set(from, 0);
        TreeSet<Pair<Integer>> st = new TreeSet<Pair<Integer>>();
        st.add(new Pair<Integer> (dist.get(from), from));
        ArrayList<Integer> history = new ArrayList<>(Collections.nCopies(graph.size(), INF));
        while (!st.isEmpty()) {
            Integer v = st.first().second;
            st.remove(st.first());

            for (Pair<Integer> _to : graph.get(v)) {
                Integer __to = _to.first;
                Integer len = _to.second;

                if (dist.get(v) + len < dist.get(__to)) {
                    st.remove(new Pair<Integer>(dist.get(__to), __to));
                    dist.set(__to, dist.get(v) + len);
                    if (dist.get(v) + len < 0) {
                        throw new IllegalArgumentException("Edge cannot have weight less than 0");
                    }
                    history.set(__to, v);
                    st.add(new Pair<Integer>(dist.get(__to), __to));
                }
            }
        }

        System.out.println("Len: " + dist.get(to));
        ArrayList<Integer> way = new ArrayList<Integer>();
        for (Integer p = to; p != from; p = history.get(p)) {
            way.add(p);
        }
        way.add(from);
        for (Integer i = way.size() - 1; i >= 0; i--) {
            System.out.print(way.get(i));
            if (i != 0)
                System.out.print("->");
        }
        System.out.println();
    }

    /**
     * Dijkstra from ONE to ALL
     * @param from
     */
    public void dijkstra2(Integer from) {
        Integer INF = 1000000000 + 7;
        ArrayList<Integer> dist = new ArrayList<>(Collections.nCopies(graph.size(), INF));
        dist.set(from, 0);
        TreeSet<Pair<Integer>> st = new TreeSet<Pair<Integer>>();
        st.add(new Pair<Integer> (dist.get(from), from));
        ArrayList<Integer> history = new ArrayList<>(Collections.nCopies(graph.size(), INF));
        while (!st.isEmpty()) {
            Integer v = st.first().second;
            st.remove(st.first());

            for (Pair<Integer> _to : graph.get(v)) {
                Integer __to = _to.first;
                Integer len = _to.second;

                if (dist.get(v) + len < dist.get(__to)) {
                    st.remove(new Pair<Integer>(dist.get(__to), __to));
                    dist.set(__to, dist.get(v) + len);
                    if (dist.get(v) + len < 0) {
                        throw new IllegalArgumentException("Edge cannot have weight less than 0");
                    }
                    history.set(__to, v);
                    st.add(new Pair<Integer>(dist.get(__to), __to));
                }
            }
        }

        for (int i=1; i<dist.size(); i++) {
            if (dist.get(i) == 1000000007)
                System.out.println("Vertex: " + i + " distance: " + "unreachable");
            else
                System.out.println("Vertex: " + i + " distance: " + dist.get(i));
        }
    }

    /**
     * Floyd from ALL to ALL + FROM => TO
     * @param from
     * @param to
     */
    public void floyd(Integer from, Integer to) {
        Integer INF = 1000000007;
        ArrayList<ArrayList<Integer>> dist = new ArrayList<>();
        Integer GRAPH_SIZE = graph.size() - 1;
        for (Integer i = 0; i < GRAPH_SIZE; i++) {
            dist.add(new ArrayList<>(Collections.nCopies(GRAPH_SIZE, INF)));
        }

        for (int i=0; i<GRAPH_SIZE; i++) {
            for (int j = 0; j < graph.get(i+1).size(); j++) {
                dist.get(i).set(graph.get(i+1).get(j).first-1, graph.get(i+1).get(j).second);
            }
        }

        for (int i=0; i<GRAPH_SIZE; i++)
            dist.get(i).set(i, 0);

        ArrayList<ArrayList<Integer>> history = new ArrayList<>();
        for (Integer i = 0; i < GRAPH_SIZE; i++) {
            history.add(new ArrayList<>(Collections.nCopies(GRAPH_SIZE, 0)));
        }

        for (int i=0; i<GRAPH_SIZE; i++) {
            for (int j=0; j<GRAPH_SIZE; j++) {
                if (i != j)
                    history.get(i).set(j, i);
                else
                    history.get(i).set(j, 0);
            }
        }

        for (int k=0; k<GRAPH_SIZE; k++) {
            System.out.println("Dist matrix on step " + k + ":");
            for (int i=0; i<GRAPH_SIZE; i++) {
                for (int j=0; j<GRAPH_SIZE; j++) {
                    if (dist.get(i).get(j) == INF)
                        System.out.print("∞" + " ");
                    else
                        System.out.print(dist.get(i).get(j) + " ");
                }
                System.out.println();
            }

            System.out.println("History matrix on step " + k + ":");
            for (int i=0; i<GRAPH_SIZE; i++) {
                for (int j=0; j<GRAPH_SIZE; j++) {
                    if (i == j)
                        System.out.print(0 + " ");
                    else
                        System.out.print(history.get(i).get(j) + 1 + " ");
                }
                System.out.println();
            }
            for (int i=0; i<GRAPH_SIZE; i++) {
                for (int j=0; j<GRAPH_SIZE; j++) {
                    if (dist.get(i).get(k) < INF && dist.get(k).get(j) < INF) {
                        if (dist.get(i).get(k) + dist.get(k).get(j) < dist.get(i).get(j)){
                            dist.get(i).set(j, dist.get(i).get(k) + dist.get(k).get(j));
                            history.get(i).set(j, history.get(k).get(j));
                        }
                    }
                }
            }
        }

        System.out.println("Dist matrix:");
        for (int i=0; i<GRAPH_SIZE; i++) {
            for (int j=0; j<GRAPH_SIZE; j++) {
                if (dist.get(i).get(j) == INF)
                    System.out.print("∞" + " ");
                else
                    System.out.print(dist.get(i).get(j) + " ");
            }
            System.out.println();
        }

        System.out.println("History matrix:");
        for (int i=0; i<GRAPH_SIZE; i++) {
            for (int j=0; j<GRAPH_SIZE; j++) {
                if (i == j)
                    System.out.print(0 + " ");
                else
                    System.out.print(history.get(i).get(j) + 1 + " ");
            }
            System.out.println();
        }

        for (int i=0; i<GRAPH_SIZE; i++) {
            for (int j=0; j<GRAPH_SIZE; j++) {
                if (dist.get(i).get(j) + dist.get(j).get(i) < 0)
                    throw new IllegalArgumentException("Cycle with negative weight exists");
            }
        }

        ArrayList<Integer> way = new ArrayList<>();
        Integer idx = to;
        while (idx != from) {
            idx = history.get(from).get(idx);
            way.add(idx + 1);
        }
        way.add(from);

        System.out.println("Way: ");
        for (int i=way.size()-1; i>=0; i--)
            System.out.print(way.get(i) + " ");
        System.out.println();
    }
}

class Pair<T extends Comparable<T>> implements Comparable<Pair<T>> {
    public T first;
    public T second;

    Pair(T first, T second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public int compareTo(Pair<T> pair) {
        if (this.first == pair.first) {
            return this.second.compareTo(pair.second);
        } else {
            return this.first.compareTo(pair.first);
        }
    }
}