import org.junit.jupiter.api.Test;

import java.util.ArrayList;

import static org.junit.jupiter.api.Assertions.*;

class DijkstraTest {

    @Test
    void test1() {
        ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[4];
        ArrayList<Integer>[] cost = (ArrayList<Integer>[])new ArrayList[4];

        for (int i = 0; i < 4; i++) {
            adj[i] = new ArrayList<Integer>();
            cost[i] = new ArrayList<Integer>();
        }

        adj[0].add(1);
        cost[0].add(1);

        adj[3].add(0);
        cost[3].add(2);

        adj[1].add(2);
        cost[1].add(2);

        adj[0].add(2);
        cost[0].add(5);

        //assertEquals(0, Dijkstra.distance(adj, cost, 1, 1));
        assertEquals(3, Dijkstra.distance(adj, cost, 0, 2));
    }

    @Test
    void test2() {
        ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[5];
        ArrayList<Integer>[] cost = (ArrayList<Integer>[])new ArrayList[5];

        for (int i = 0; i < 5; i++) {
            adj[i] = new ArrayList<Integer>();
            cost[i] = new ArrayList<Integer>();
        }

        adj[0].add(1);
        cost[0].add(4);

        adj[0].add(2);
        cost[0].add(2);

        adj[1].add(2);
        cost[1].add(2);

        adj[2].add(1);
        cost[2].add(1);

        adj[1].add(3);
        cost[1].add(2);

        adj[2].add(4);
        cost[2].add(4);

        adj[4].add(3);
        cost[4].add(1);

        adj[1].add(4);
        cost[1].add(3);

        adj[2].add(3);
        cost[2].add(4);

        assertEquals(6, Dijkstra.distance(adj, cost, 0, 4));
    }

    @Test
    void test3() {
        ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[3];
        ArrayList<Integer>[] cost = (ArrayList<Integer>[])new ArrayList[3];

        for (int i = 0; i < 3; i++) {
            adj[i] = new ArrayList<Integer>();
            cost[i] = new ArrayList<Integer>();
        }

        adj[0].add(1);
        cost[0].add(7);

        adj[0].add(2);
        cost[0].add(5);

        adj[1].add(2);
        cost[1].add(2);

        assertEquals(-1, Dijkstra.distance(adj, cost, 2, 1));
    }

    @Test
    void test4() {
        ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[5];
        ArrayList<Integer>[] cost = (ArrayList<Integer>[])new ArrayList[5];

        for (int i = 0; i < 5; i++) {
            adj[i] = new ArrayList<Integer>();
            cost[i] = new ArrayList<Integer>();
        }

        adj[0].add(1);
        cost[0].add(5);

        adj[1].add(2);
        cost[1].add(1);

        adj[2].add(3);
        cost[2].add(1);

        adj[3].add(4);
        cost[3].add(1);

        adj[2].add(4);
        cost[2].add(2);

        assertEquals(3, Dijkstra.distance(adj, cost, 1, 4));
    }

    @Test
    void test6() {
        ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[9];
        ArrayList<Integer>[] cost = (ArrayList<Integer>[])new ArrayList[9];

        for (int i = 0; i < 9; i++) {
            adj[i] = new ArrayList<Integer>();
            cost[i] = new ArrayList<Integer>();
        }

        adj[0].add(1);
        cost[0].add(4);

        adj[1].add(0);
        cost[1].add(4);

        adj[0].add(7);
        cost[0].add(8);

        adj[7].add(0);
        cost[7].add(8);

        adj[1].add(7);
        cost[1].add(11);

        adj[7].add(1);
        cost[7].add(11);

        adj[1].add(2);
        cost[1].add(8);

        adj[2].add(1);
        cost[2].add(8);

        adj[7].add(8);
        cost[7].add(7);

        adj[8].add(7);
        cost[8].add(7);

        adj[7].add(6);
        cost[7].add(1);

        adj[6].add(7);
        cost[6].add(1);

        adj[2].add(8);
        cost[2].add(2);

        adj[8].add(2);
        cost[8].add(2);

        adj[8].add(6);
        cost[8].add(6);

        adj[6].add(8);
        cost[6].add(6);

        adj[2].add(3);
        cost[2].add(7);

        adj[3].add(2);
        cost[3].add(7);

        adj[2].add(5);
        cost[2].add(4);

        adj[5].add(2);
        cost[5].add(4);

        adj[6].add(5);
        cost[6].add(2);

        adj[5].add(6);
        cost[5].add(2);

        adj[3].add(5);
        cost[3].add(14);

        adj[5].add(3);
        cost[5].add(14);

        adj[3].add(4);
        cost[3].add(9);

        adj[4].add(3);
        cost[4].add(9);

        adj[4].add(5);
        cost[4].add(10);

        adj[5].add(4);
        cost[5].add(10);

        assertEquals(21, Dijkstra.distance(adj, cost, 0, 4));
    }

    @Test
    void test11() {
        ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[5];
        ArrayList<Integer>[] cost = (ArrayList<Integer>[])new ArrayList[5];

        for (int i = 0; i < 5; i++) {
            adj[i] = new ArrayList<Integer>();
            cost[i] = new ArrayList<Integer>();
        }

        adj[2].add(4);
        cost[2].add(49438153);

        adj[1].add(2);
        cost[1].add(78072041);

        adj[2].add(3);
        cost[2].add(12409612);

        adj[0].add(2);
        cost[0].add(88526216);

        adj[4].add(1);
        cost[4].add(6876525);

        adj[0].add(3);
        cost[0].add(28703032);

        adj[3].add(0);
        cost[3].add(24629785);

        adj[3].add(4);
        cost[3].add(96300300);

        adj[3].add(2);
        cost[3].add(317823);

        adj[1].add(4);
        cost[1].add(22632987);

        assertEquals(56632501, Dijkstra.distance(adj, cost, 3, 1));
    }
}