import java.util.TreeSet;

public class Test {
    public static void route(int[][] mat){
        Graph graph = new Graph(mat);
        TreeSet<Node> treeSet = new TreeSet<>();
        graph.getNode(0, 0).setValue(0);
        treeSet.add(graph.getNode(0,0));
        graph.print();
        System.out.println();
        while(!treeSet.isEmpty()){
            Node tempNode = treeSet.pollFirst();
            tempNode.setFlag(true);
            int tempX = tempNode.x;
            int tempY = tempNode.y;
            int value = tempNode.getValue();
            Node tempNodeO = graph.getNode(tempX - 1, tempY);
            if(!tempNodeO.isFlag()){
                int tempValue = tempNodeO.getWeight() + value;
                if(tempNodeO.getValue() > tempValue){
                    tempNodeO.setValue(tempValue);
                    tempNodeO.setPrev(tempNode);
                    treeSet.add(tempNodeO);
                }

            }
            tempNodeO = graph.getNode(tempX, tempY - 1);
            if(!tempNodeO.isFlag()){
                int tempValue = tempNodeO.getWeight() + value;
                if(tempNodeO.getValue() > tempValue){
                    tempNodeO.setValue(tempValue);
                    tempNodeO.setPrev(tempNode);
                    treeSet.add(tempNodeO);
                }
            }
            tempNodeO = graph.getNode(tempX, tempY + 1);
            if(!tempNodeO.isFlag()){
                int tempValue = tempNodeO.getWeight() + value;
                if(tempNodeO.getValue() > tempValue){
                    tempNodeO.setValue(tempValue);
                    tempNodeO.setPrev(tempNode);
                    treeSet.add(tempNodeO);
                }

            }
            tempNodeO = graph.getNode(tempX + 1, tempY);
            if(!tempNodeO.isFlag()){
                int tempValue = tempNodeO.getWeight() + value;
                if(tempNodeO.getValue() > tempValue){
                    tempNodeO.setValue(tempValue);
                    tempNodeO.setPrev(tempNode);
                    treeSet.add(tempNodeO);
                }

            }
        }
        graph.print();
        System.out.println(0);
        System.out.println("Вес минимального пути: " + graph.getNode(graph.getNROW() - 1, graph.getNCOL() - 1).getValue());
        System.out.println("Путь: ");
        Node tempNode = graph.getNode(graph.getNROW() - 1, graph.getNCOL() - 1);
        while (tempNode.getPrev() != null){
            System.out.print(tempNode + "; ");
            tempNode = tempNode.getPrev();
        }
    }

    public static void main(String[] args) {
        int[][] mat = new int[5][6];
        mat[0][0] = 1; mat[0][1] = 100; mat[0][2] = 1; mat[0][3] = 1; mat[0][4] = 1; mat[0][5] = 100;
        mat[1][0] = 1; mat[1][1] = 100; mat[1][2] = 1; mat[1][3] = 100; mat[1][4] = 1; mat[1][5] = 100;
        mat[2][0] = 1; mat[2][1] = 1; mat[2][2] = 1; mat[2][3] = 100; mat[2][4] = 1; mat[2][5] = 100;
        mat[3][0] = 100; mat[3][1] = 100; mat[3][2] = 100; mat[3][3] = 100; mat[3][4] = 1; mat[3][5] = 100;
        mat[4][0] = 100; mat[4][1] = 100; mat[4][2] = 100; mat[4][3] = 100; mat[4][4] = 1; mat[4][5] = 100;
        route(mat);
    }
}