import org.junit.Test;

import java.util.*;

public class GraphTest {
    Node[] nodes;
    List<Node> ans=new ArrayList<Node>();
    class Node{
        int ID;
        Map<Node,Integer> nexts;

        public Node(int ID) {
            this.ID = ID;
            this.nexts=new HashMap<Node,Integer>();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return ID == node.ID;
        }

        @Override
        public int hashCode() {
            return Objects.hash(ID);
        }
    }

    class Link{
        Node curr;
        Link pre;
        int length;

        public Link(Node curr, Link pre,int length) {
            this.curr = curr;
            this.pre = pre;
            this.length=length;
        }
    }

    void matrixToGraph(int[][] matrix){
        int len=matrix.length;
        nodes=new Node[len];
        for(int i=0;i<len;i++){
            Node curr=nodes[i];
            if(curr==null){
                curr=new Node(i);
                nodes[i]=curr;
            }
            for(int j=0;j<len;j++){
                Node next=nodes[j];
                if(next==null){
                    next=new Node(j);
                    nodes[j]=next;
                }
                if(matrix[i][j]>0){
                    curr.nexts.put(next,matrix[i][j]);
                }
            }
        }
    }

    void search(Node start,Node end){
//        Queue<Link> nexts=new LinkedList<Link>();
        Queue<Link> nexts=new PriorityQueue<Link>((a,b)->(a.length-b.length));
        Map<Node,Integer> seen=new HashMap<Node,Integer>();
        nexts.add(new Link(start,null,0));
        seen.put(start,0);
        Link goodAnswer=null;
        while (!nexts.isEmpty()){
            Link link=nexts.poll();
            Node curr=link.curr;
            if(curr.equals(end)){
                goodAnswer=link;
                break;
            }
            int currLength=link.length;
            for(Node next:curr.nexts.keySet()){
                int length=seen.getOrDefault(next,Integer.MAX_VALUE>>1);
                if(currLength+curr.nexts.get(next)<length){
                    nexts.add(new Link(next,link,currLength+curr.nexts.get(next)));
                    seen.put(next,currLength+curr.nexts.get(next));
                }
            }
        }
        if(goodAnswer!=null){
            while (goodAnswer!=null){
                ans.add(goodAnswer.curr);
                goodAnswer=goodAnswer.pre;
            }
        }
        Collections.reverse(ans);
    }

    @Test
    public void test(){
        int[][] matrix={
                {0,1,-1,3,-1},
                {-1,0,5,1,-1},
                {-1,2,0,-1,2},
                {-1,-1,-1,0,3},
                {-1,-1,-1,-1,0}
        };
        matrixToGraph(matrix);

        Node start=nodes[0];
        Node end=nodes[nodes.length-1];

        search(start,end);

        for(Node node:ans){
            System.out.print(node.ID+"->");
        }
    }
}