---
title: 743. Network Delay Time
tags: graph
description: share source code.
---

# 743. Network Delay Time

class Solution {
    // 不知道終點, 只能最小 dist 中取最大
    // 這題 times = Edge
    
    static class Edge{
        int val;
        int w;
        
        public Edge(int val, int w){
            this.val = val;
            this.w = w;
        }
    }
    
    static int INF = Integer.MAX_VALUE/2;
  
    public int networkDelayTime(int[][] times, int n, int k) {
      
        List<Edge> [] graph = new ArrayList[n + 1];
        Arrays.setAll(graph, v -> new ArrayList<>());
        for(int time [] : times){
            graph[time[0]].add(new Edge(time[1], time[2]));
        }
        
        
        PriorityQueue<Edge> q = new PriorityQueue<>( ( a, b) -> a.w - b.w);
        
        
        int dist [] = new int [n + 1];
        Arrays.fill(dist, INF);
        
        q.offer(new Edge(k, 0));
            
        while(!q.isEmpty()){
             Edge u =  q.poll();
                 
             if(dist[u.val] != INF){
                continue;
             } 
            
             dist[u.val]  = u.w;// dist[v.val] = u.w + v.w;
               
             for(Edge v : graph[u.val]){
                q.offer(new Edge(v.val, u.w + v.w));
             }     
        }
        
       int max = Integer.MIN_VALUE; 
       for(int i = 1; i <= n; i++){
           max = Math.max(dist[i], max);
       }     
       
       return max == INF ? -1 : max;
    }
}