有 N 個網絡節點，標記為 1 到 N。

給定一個列表 times，表示信號經過有向邊的傳遞時間。 times[i] = (u, v, w)，其中 u 是源節點，v 是目標節點， w 是一個信號從源節點傳遞到目標節點的時間。
現在，我們從某個節點 K 發出一個信號。需要多久才能使所有節點都收到信號？如果不能使所有節點收到信號，返回 -1。

示例：

輸入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
輸出：2

代碼

class Solution {HashMap<Integer, List<int[]>> map;HashMap<Integer,Integer> dist;public int networkDelayTime(int[][] times, int N, int K) {dist=new HashMap<>();map=new HashMap<>();boolean[] check=new boolean[N+1];for(int[] time:times)//構造鄰接表{    if(!map.containsKey(time[0]))map.put(time[0], new ArrayList<int[]>());map.get(time[0]).add(new int[]{time[1],time[2]});}for(int i=1;i<=N;i++)dist.put(i,Integer.MAX_VALUE); dist.put(K,0);while (true){int curDist=Integer.MAX_VALUE;int curNode=-1;for(int i=1;i<=N;i++)if(!check[i]&&dist.get(i)<curDist)//找出當前距離起點的最近的節點{curDist=dist.get(i);curNode=i;}if(curNode<0) break;//遍歷完了所有節點check[curNode]=true;//當前節點已經被訪問if(map.containsKey(curNode)){for(int[] next:map.get(curNode))//更新鄰接點與起點的最小距離dist.put(next[0], Math.min(next[1]+dist.get(curNode),dist.get(next[0])));}}int cnt=0;for(int c:dist.values())//遍歷所有的節點到起點的距離{   if(c==Integer.MAX_VALUE) return -1;cnt= Math.max(c,cnt);}return cnt;}
}

堆實現代碼

    HashMap<Integer, List<int[]>> map;public int networkDelayTime(int[][] times, int N, int K) {HashMap<Integer,Integer> dist=new HashMap<>();map=new HashMap<>();boolean[] check=new boolean[N+1];for(int[] time:times)//構造鄰接表{    if(!map.containsKey(time[0]))map.put(time[0], new ArrayList<int[]>());map.get(time[0]).add(new int[]{time[1],time[2]});}PriorityQueue<int[]> priorityQueue=new PriorityQueue<>(((o1, o2) -> o1[0]-o2[0]));//按距離從小到大priorityQueue.offer(new int[]{0,K});//將起點加入優先隊列while (!priorityQueue.isEmpty()){int[] temp=priorityQueue.poll();int d=temp[0],node=temp[1];if(dist.containsKey(node)) continue;//已經確定了距離的不再訪問dist.put(node,d);if(map.containsKey(node))for(int[] next:map.get(node))//將鄰接點到起點的距離加入優先隊列{ if(!dist.containsKey(next[0]));{priorityQueue.offer(new int[]{d+next[1],next[0]});}}}if(dist.size()!=N) return -1;int cnt=0;for(int c:dist.values()){cnt= Math.max(c,cnt);}return cnt;}