题目描述：

LeetCode 743. Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

题目大意：

给定N个节点，有向边集times，边用(u, v, w)表示(源点，汇点，权重)

从节点K向邻近节点广播消息，收到消息的节点重复此过程。求所有节点都收到消息所需要的最短时间

若存在消息无法送达的节点，返回-1

解题思路：

单源最短路（Dijkstra） + 优先队列

用邻接表构图，从K点出发执行Dijkstra算法

记录每个顶点的访问时间并更新最大值ans

最后判断访问的顶点数是否等于N，若不等于则返回-1，否则返回ans

Java代码：

class Solution {
    class Pair implements Comparable<Pair>{
        public int node;
        public int time;
        public Pair(int node, int time) {
            this.node = node;
            this.time = time;
        }
        public int compareTo(Pair p) {
            return time - p.time;
        }
    }
    public int networkDelayTime(int[][] times, int N, int K) {
        PriorityQueue<Pair> queue = new PriorityQueue<>();
        HashSet<Integer> visits = new HashSet<>();
        HashMap<Integer, HashMap<Integer, Integer>> edges = new HashMap<>();
        for (int[] t : times) {
            HashMap<Integer, Integer> edge = edges.get(t[0]);
            if (edge == null) {
                edge = new HashMap<>();
                edges.put(t[0], edge);
            }
            edge.put(t[1], t[2]);
        }
        int ans = 0;
        queue.add(new Pair(K, 0));
        while (!queue.isEmpty()) {
            Pair front = queue.poll();
            if (visits.contains(front.node)) continue;
            ans = front.time;
            visits.add(front.node);
            HashMap<Integer, Integer> edge = edges.get(front.node);
            if (edge == null) continue;
            for (Map.Entry<Integer, Integer> entry : edge.entrySet()) {
                queue.add(new Pair(entry.getKey(), front.time + entry.getValue()));
            }
        }
        return visits.size() < N ? -1 : ans;
    }
}

 

本文链接：http://bookshadow.com/weblog/2017/12/10/leetcode-network-delay-time/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码