lintcode 1057 · 网络延迟时间【图，BFS,中等】

题目链接，描述

https://www.lintcode.com/problem/1057

有 N个网络节点，从 1 到 N标记.

给定 times，一个旅行时间和有向边列表 times[i] = (u, v, w)，其中u 是起始点， v是目标点， w是一个信号从起始到目标点花费的时间。

现在，我们从一个特定节点 K发出信号，所有节点收到信号需要花费多长时间? 如果不可能，返回-1。


1.N 是 [1, 100]内的整数.
2.K 位于 [1, N]范围内.
3. times 的长度在范围 [1, 6000] 内.
4. 所有边 times[i] = (u, v, w) 将会有 1 <= u, v <= N 以及1 <= w <= 100.

样例
样例 1:
	输入:  times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
	输出:  2

样例 2:
	输入: times = [[1,2,1],[1,2,2]], N = 2, K = 1
	输出:  1

	解释:
	两条路选择最短的。

思路

SPFA: 首先，bfs也可以用来做有向图，边长不固定的最短路径
这个题里面，关键是bfs要把所有的路径都走一遍，并记录到达当前点的最小值是什么。
如果到达当前点的cost比之前记录的cost低，那么就再放到queue里面。这种方法叫什么pfsa之类的。
反正记住一点，bfs继续走下去，值更小的时候更新值，并再放到queue里面。
最后把所有的cost都看一遍，找到其中的最大值。

代码

public class Solution {
    /**
     * @param times: a 2D array
     * @param n: an integer
     * @param k: an integer
     * @return: how long will it take for all nodes to receive the signal
     */
    public int networkDelayTime(int[][] times, int n, int k) {
         // SPFA
        /*
        首先，bfs也可以用来做有向图，边长不固定的最短路径
        这个题里面，关键是bfs要把所有的路径都走一遍，并记录到达当前点的最小值是什么。
        如果到达当前点的cost比之前记录的cost低，那么就再放到queue里面。这种方法叫什么pfsa之类的。
        反正记住一点，bfs继续走下去，值更小的时候更新值，并再放到queue里面。
        最后把所有的cost都看一遍，找到其中的最大值。
         */
      Map<Integer,Set<Info>> graph = new HashMap<>();
        for (int[] arr : times) {
            int a= arr[0],b=arr[1],c=arr[2];
            if(!graph.containsKey(a))
                graph.put(a,new HashSet<>());
            graph.get(a).add(new Info(b,c));
        }

        Map<Integer,Integer> distances = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(k);
        distances.put(k,0);

        while (!queue.isEmpty()){
            int cur= queue.poll();
            int curdis = distances.get(cur);
            if(!graph.containsKey(cur))
                continue;

            for(Info next: graph.get(cur)){
                if(!distances.containsKey(next.data) || next.dis+curdis < distances.get(next.data)){
                    distances.put(next.data,next.dis+curdis);
                    queue.add(next.data);
                }
            }
        }

        if(distances.size()!=n)
            return -1;

        int ans =0;
        for(int dis: distances.values()){
            ans=Math.max(ans,dis);
        }
        return ans;
    }

    static class Info {
        int data;
        int dis;

        public Info(int d, int d1) {
            data = d;
            dis = d1;
        }
    }

}