package algorithms.leetcode;

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /*int[][] graph = {
                {2,1,1},
                {2,3,1},
                {3,4,1}
        };
        int N = 4;
        int K = 2;*/

        /*int[][] graph = {{2,1,1},{2,3,1},{3,4,1}};
        int N = 4;
        int K = 2;*/

        /*int[][] graph = {{1,2,1}};
        int N = 2;
        int K = 1;*/

        /*int[][] graph = {{1,2,1},{2,1,3}};
        int N = 2;
        int K = 2;*/

        /*int[][] graph = {{1,2,1},{2,3,2}};
        int N = 3;
        int K = 1;*/

        /*int[][] graph = {{1,2,1},{2,1,3}};
        int N = 2;
        int K = 2;*/

        int[][] graph = {{1,2,1},{2,3,2},{1,3,2}};
        int N = 3;
        int K = 1;

        /*
        trono en este caso
        [[2,4,10],[5,2,38],[3,4,33],[4,2,76],[3,2,64],[1,5,54],[1,4,98],[2,3,61],[2,1,0],[3,5,77],[5,1,34],[3,1,79],[5,3,2],[1,2,59],[4,3,46],[5,4,44],[2,5,89],[4,5,21],[1,3,86],[4,1,95]]
        5
        1
        * */

        Solution.networkDelayTime(graph, N, K);
    }

    public static int networkDelayTime(int[][] times, int N, int K) {
        if (times.length == 0) return - 1;

        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] time : times) {
            if (!graph.containsKey(time[0])) {
                graph.put(time[0], new HashMap<>());
            }
            graph.get(time[0]).put(time[1], time[2]);
        }

        if (!graph.containsKey(K)) return -1;

        Map<Integer, Integer> visited = new HashMap<>();
        boolean[] alreadyVisited = new boolean[N + 1];
        PriorityQueue<Integer> maxResult = new PriorityQueue<>(N, Collections.reverseOrder());
        depthFirstSearch(graph, K, 0, visited, alreadyVisited);

        if (visited.size() != N) return -1;

        for (Map.Entry<Integer, Integer> iterateOverVisited : visited.entrySet()) {
            maxResult.add(iterateOverVisited.getValue());
        }
        return maxResult.peek();
    }

    public static void depthFirstSearch(Map<Integer, Map<Integer, Integer>> graph, int currVal, int currTime, Map<Integer, Integer> visited, boolean[] alreadyVisited) {
        if (!alreadyVisited[currVal])
            visited.put(currVal, currTime);
        else
            visited.put(currVal, Math.min(currTime, visited.get(currVal)));
        if (graph.containsKey(currVal) && !alreadyVisited[currVal]) {
            for (Map.Entry<Integer, Integer> neighboors : graph.get(currVal).entrySet()) {
                alreadyVisited[currVal] = true;
                depthFirstSearch(graph, neighboors.getKey(), neighboors.getValue() + currTime, visited, alreadyVisited);
            }
        } else {
            alreadyVisited[currVal] = true;
        }
    }
}