# 0743. Network Delay Time
###### tags: `Leetcode` `Medium` `Dijkstra`
Link: https://leetcode.com/problems/network-delay-time/description/
## 思路
dijk找到从起始点k到每个点的最短距离
取最大的就是答案
如果有一个还是```Integer.MAX_VALUE```就说明到不了 ```return -1```
## Code

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> graph = new ArrayList<>();
        for(int i=0; i<n; i++) graph.add(new ArrayList<>());
        for(int[] t:times){
            graph.get(t[0]-1).add(new int[]{t[1]-1, t[2]});
        }
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[1]-b[1]));
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k-1] = 0;
        pq.add(new int[]{k-1, 0});
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            for(int[] next:graph.get(curr[0])){
                if(dist[next[0]]>dist[curr[0]]+next[1]){
                    dist[next[0]] = dist[curr[0]]+next[1];
                    pq.add(new int[]{next[0], dist[next[0]]});
                }
            }
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            if(dist[i]==Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
}