[5/14] 43. Network Delay Time

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        int ret = 0;
        typedef tuple<int, int> edge;
        unordered_set<int> s;
        priority_queue<edge, vector<edge>, greater<edge>> q;
        vector<vector<edge>> v(n+1);
        for(auto &t : times) v[t[0]].emplace_back(t[2], t[1]);
        q.emplace(0, k);
        while(s.size() != n && !q.empty()) {
            auto [time, node] = q.top();
            q.pop();
            if (s.find(node) != s.end()) continue;
            ret = time;
            s.emplace(node);            
            for(auto [delta, next_node] : v[node]) if (s.find(next_node) == s.end()) q.emplace(time + delta, next_node);
        }
        return s.size() == n ? ret : -1;
    }
};

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int> visited(n + 1, 1e9);
        vector<vector<vector<int>>> edges(n + 1);
        stack<int> st;
        
        for (auto &time : times) {
            edges[time[0]].push_back({time[1], time[2]});
        }
        
        st.push(k);
        visited[k] = 0;
        while (!st.empty()) {
            int curr = st.top(); st.pop();
            for (auto &edge : edges[curr]) {
                if (visited[edge[0]] > visited[curr] + edge[1]) {
                    visited[edge[0]] = visited[curr] + edge[1];
                    st.push(edge[0]);
                }
            }
        }
        int result = 0;
        for (int i = 1; i < visited.size(); ++i) {
            result = max(result, visited[i]);
        }
        return result == 1e9 ? -1 : result;
    }
};

class Solution {
    
    // adj nodes
    Map<Integer, List<Pair<Integer, Integer>>> adjMap = new HashMap<>();
    
    
    public int networkDelayTime(int[][] times, int n, int k) {
        // 2 1 1 = from 2 to 1, 1 second
        // 2 3 1 = from 2 to 3, 1 second
        // 3 4 1 = from 3 to 4, 1 second
        
        // n = total number of nodes
        // k = initial node
        
        for(int[] time : times){
            int from = time[0];
            int to = time[1];
            int timeCost = time[2];
            
            adjMap.putIfAbsent(from, new ArrayList<>());
            adjMap.get(from).add(new Pair(timeCost, to));
        }
        
        int[] vertex = new int[n+1];
        Arrays.fill(vertex, Integer.MAX_VALUE);
        
        dijkstra(vertex, k, n);
        
        int result = Integer.MIN_VALUE;
        for(int i=1; i<=n; i++){
            result = Math.max(result, vertex[i]);
        }
        
        
        
        return result == Integer.MAX_VALUE? -1 : result;
    }
    
    
    private void dijkstra(int[] vertex, int origin, int n){
        Queue<Pair<Integer, Integer>> pq = new PriorityQueue<Pair<Integer,Integer>>(Comparator.comparing(Pair::getKey));
        
        pq.add(new Pair(0, origin));
        
        // init time for starting node = 0
        vertex[origin] = 0;
        
        while(!pq.isEmpty()){
            Pair<Integer, Integer> topPair = pq.remove();
            
            int currNode = topPair.getValue();
            int currNodeTime = topPair.getKey();
            
            if(currNodeTime > vertex[currNode]){
                continue;
            }
            
            if(!adjMap.containsKey(currNode)){
                continue;
            }
            
            // Prepartage the signal
            for(Pair<Integer, Integer> edge: adjMap.get(currNode)){
                int time = edge.getKey();
                int adjNode = edge.getValue();
                
                if(vertex[adjNode] > currNodeTime + time){
                    vertex[adjNode] = currNodeTime + time;
                    pq.add(new Pair(vertex[adjNode], adjNode));
                }
            }
        }
    }
    
}