lab5_part2

import javax.swing.*;
import java.io.File;
import java.io.FileNotFoundException;
import java.lang.reflect.Array;
import java.security.InvalidParameterException;
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 - Bellman from ONE to ALL \n 2 - Bellman FROM => TO \n 3 - Johnson from ONE to ALL \n 4 - Johnson FROM => TO \n 5 - terminate");

                Scanner consoleScanner = new Scanner(System.in);

                Integer input = consoleScanner.nextInt();

                switch (input) {
                    case 1: {
                        System.out.println("Bellman from ONE to ALL");
                        Integer v = consoleScanner.nextInt();

                        graph.bellman(v);
                        break;
                    }
                    case 2: {
                        System.out.println("Bellman FROM => TO");
                        Integer from = consoleScanner.nextInt();
                        Integer to = consoleScanner.nextInt();

                        graph.bellman2(from, to);
                        break;
                    }
                    case 3: {
                        System.out.println("Johnson from ONE to ALL");
                        Integer from = consoleScanner.nextInt();

                        graph.johnson(from, -1);
                        break;
                    }
                    case 4: {
                        System.out.println("Johnson FROM=>TO");
                        Integer from = consoleScanner.nextInt();
                        Integer to = consoleScanner.nextInt();

                        graph.johnson(from, to);
                        break;
                    }
                    case 5: {
                        exit(0);
                    }

                }
            }

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

class Edge {

    public Integer from;
    public Integer to;
    public Integer weight;

    Edge(Integer from, Integer to, Integer weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return from + "=>" + to + " " + weight;
    }
}

class Graph {

    private ArrayList<ArrayList<Pair<Integer> > > graph;
    private ArrayList<Boolean> used;
    private ArrayList<Edge> edges = new ArrayList<>();

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

        for (int i = 0; i < graph.size(); i++) {
            for (int j = 0; j < graph.get(i).size(); j++) {
                edges.add(new Edge(i, graph.get(i).get(j).first, graph.get(i).get(j).second));
            }
        }

        this.graph = graph;
    }

    /**
     * Bellman, from ONE to ALL
     * @param v
     */
    public void bellman(Integer v) {
        Integer INF = 1000000000 + 7;
        ArrayList<ArrayList<Integer> > dist = new ArrayList<>();
        for (int i = 0; i < graph.size(); i++) {
            ArrayList<Integer> list = new ArrayList<>(Collections.nCopies(graph.size(), INF));
            dist.add(list);
        }
        dist.get(0).set(v, 0);
        for (int i = 1; i < graph.size(); i++) {
            for (int j = 1; j < graph.size(); j++) {
                dist.get(i).set(j, dist.get(i-1).get(j));
                for (Edge e : edges) {
                    if (dist.get(i).get(e.to) > dist.get(i-1).get(e.from) + e.weight) {
                        dist.get(i).set(e.to, dist.get(i-1).get(e.from) + e.weight);
                    }
                }
            }
        }

        for (Edge e : edges) {
            if (dist.get(graph.size() - 1).get(e.to) > dist.get(graph.size() - 1).get(e.from) + e.weight)
                throw new InvalidParameterException("Cycle with negative weight found!");
        }

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

    /**
     * Bellman, FROM => TO
     * @param from
     * @param to
     */
    public void bellman2(Integer from, Integer to) {
        Integer INF = 1000000000 + 7;
        ArrayList<ArrayList<Integer> > dist = new ArrayList<>();
        ArrayList<Integer> history = new ArrayList<>(Collections.nCopies(graph.size(), 0));
        for (int i = 0; i < graph.size(); i++) {
            ArrayList<Integer> list = new ArrayList<>(Collections.nCopies(graph.size(), INF));
            dist.add(list);
        }
        dist.get(0).set(from, 0);
        for (int i = 1; i < graph.size(); i++) {
            for (int j = 1; j < graph.size(); j++) {
                dist.get(i).set(j, dist.get(i-1).get(j));
                for (Edge e : edges) {
                    if (dist.get(i).get(e.to) > dist.get(i-1).get(e.from) + e.weight) {
                        dist.get(i).set(e.to, dist.get(i-1).get(e.from) + e.weight);
                        history.set(e.to, e.from);
                    }
                }
            }
        }

        for (Edge e : edges) {
            if (dist.get(graph.size() - 1).get(e.to) > dist.get(graph.size() - 1).get(e.from) + e.weight)
                throw new InvalidParameterException("Cycle with negative weight found!");
        }

        ArrayList<Integer> way = new ArrayList<>();
        for (Integer i = to; i != from; i = history.get(i)) {
            way.add(i);
        }
        way.add(from);

        System.out.println("Way " + from + " => " + to);
        for (Integer i = way.size() - 1; i >= 0; i--) {
            if (i != 0)
                System.out.print(way.get(i) + "=>");
            else
                System.out.print(way.get(i));
        }
        System.out.println();
    }

    public void johnson(Integer from, Integer to) {
        /**
         * Create G' graph(add S)
         */
        ArrayList<ArrayList<Pair<Integer> > > graph1 = new ArrayList<>();
        ArrayList<Edge> edges1 = new ArrayList<>();
        for (int i=0; i<graph.size(); i++) {
            ArrayList<Pair<Integer>> list = new ArrayList<>();
            for (int j=0; j<graph.get(i).size(); j++) {
                list.add(graph.get(i).get(j));
            }
            graph1.add(list);
        }
        for (Integer i = 0; i < edges.size(); i++) {
            Edge e = edges.get(i);
            edges1.add(new Edge(e.from, e.to, e.weight));
        }

        for (int i=0; i<graph1.size(); i++) {
            graph1.get(i).add(new Pair<Integer>(graph1.size(), 0));
        }

        ArrayList<Pair<Integer>> list = new ArrayList<>();

        for (int i=0; i<graph1.size(); i++) {
            list.add(new Pair<>(i, 0));
            edges1.add(new Edge(graph1.size(), i, 0));
        }

        graph1.add(list);

        Integer s = graph1.size() - 1;

        /**
         * Bellman
         */
        Integer INF = 1000000000 + 7;
        ArrayList<ArrayList<Integer> > dist = new ArrayList<>();
        for (int i = 0; i < graph1.size(); i++) {
            ArrayList<Integer> list1 = new ArrayList<>(Collections.nCopies(graph1.size(), INF));
            dist.add(list1);
        }
        dist.get(0).set(s, 0);
        for (int i = 1; i < graph1.size(); i++) {
            for (int j = 1; j < graph1.size(); j++) {
                dist.get(i).set(j, dist.get(i-1).get(j));
                for (Edge e : edges1) {
                    if (dist.get(i).get(e.to) > dist.get(i-1).get(e.from) + e.weight) {
                        dist.get(i).set(e.to, dist.get(i-1).get(e.from) + e.weight);
                    }
                }
            }
        }

        for (Edge e : edges1) {
            if (dist.get(graph1.size() - 1).get(e.to) > dist.get(graph1.size() - 1).get(e.from) + e.weight)
                throw new InvalidParameterException("Cycle with negative weight found!");
        }

        /**
         * Determine h(v)
         */
        ArrayList<Integer> h = new ArrayList<>(Collections.nCopies(graph1.size(), 0));
        for (int i=0; i<dist.size(); i++) {
            h.set(i, dist.get(graph1.size() - 2).get(i));
        }

        /**
         * Determine new weights w'(u, v) = w(u, v) + h(u) - h(v)
         */
        for (Edge e : edges1) {
            e.weight = e.weight + h.get(e.from) - h.get(e.to);
        }

        for (Integer i=0; i<graph1.size(); i++) {
            for (Integer j=0; j<graph1.get(i).size(); j++) {
                for (Edge e : edges1) {
                    if (e.from == i && e.to == graph1.get(i).get(j).first) {
                        graph1.get(i).get(j).second = e.weight;
                    }
                }
            }
        }

        /**
         * Dijkstra
         */
        ArrayList<ArrayList<Integer> > D = new ArrayList<>();
        ArrayList<ArrayList<Integer> > historyD = new ArrayList<>();
        D.add(new ArrayList<>(Collections.nCopies(graph1.size(), INF)));
        historyD.add(new ArrayList<>(Collections.nCopies(graph1.size(), INF)));
        for (Integer u = 1; u < graph1.size() - 1; u++) {
            ArrayList<Integer> _dist = new ArrayList<>(Collections.nCopies(graph1.size(), INF));
            _dist.set(u, 0);
            TreeSet<Pair<Integer>> st = new TreeSet<Pair<Integer>>();
            st.add(new Pair<Integer>(_dist.get(u), u));
            ArrayList<Integer> history = new ArrayList<>(Collections.nCopies(graph1.size(), INF));
            while (!st.isEmpty()) {
                Integer v = st.first().second;
                st.remove(st.first());
                if (v == graph1.size()-1)
                    continue;

                for (Pair<Integer> _to : graph1.get(v)) {
                    Integer __to = _to.first;
                    Integer len = _to.second;
                    if (__to == s)
                        continue;

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

            D.add(_dist);
            historyD.add(history);
        }

        /**
         * new distances d(u, v) = d'(u, v) - h(u) + h(v)
         */
        ArrayList<ArrayList<Integer> > newD = new ArrayList<ArrayList<Integer>>();
        for (int i=0; i<graph1.size(); i++) {
            ArrayList<Integer> list2 = new ArrayList<>(Collections.nCopies(graph1.size(), 0));
            newD.add(list2);
        }
        for (int i=1; i<graph1.size()-1; i++) {
            for (int j=1; j<graph1.size()-1; j++) {
                newD.get(i).set(j, D.get(i).get(j) - h.get(i) + h.get(j));
            }
        }

        if (to == -1) {
            for (int i=1; i<graph1.size()-1; i++) {
                System.out.println("Vertex " + i + " length: " + newD.get(from).get(i));
            }
        } else {
            ArrayList<Integer> way = new ArrayList<>();
            for (Integer i = to; i != from; i = historyD.get(from).get(i)) {
                way.add(i);
                if (historyD.get(from).get(i) == INF)
                    break;
            }
            way.add(from);

            System.out.println("Length: " + newD.get(from).get(to));
            for (Integer i = way.size() - 1; i >= 0; i--) {
                System.out.print(way.get(i));
                if (i != 0)
                    System.out.print("=>");
            }
            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);
        }
    }

    @Override
    public String toString() {
        return first + "-" + second;
    }
}