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个节点的有向图，求从结点 K 到所有结点的单源最短路，然后，从中选择最长的一条路所用的时间即为答案。

解题思路

考虑到N较小(n<=100)可以直接用N^3的Floyd算法求解。

如果要更好的效率，那么就用SPFA，跑一次就能求出k到所有点的最短距离。

SPFA就不多说了，搞过OI的都知道，又快又好用。