LWC 62：743. Network Delay Time

LWC 62：743. Network Delay Time

Problem:

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:

N will be in the range [1, 100].

K will be in the range [1, N].

The length of times will be in the range [1, 6000].

All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

Java版：

```    class Edge{
int from;
int to;
int weight;

Edge(int from, int to, int weight){
this.from = from;
this.to = to;
this.weight = weight;
}
}

class Node implements Comparable<Node>{

int v;
int dist;

Node(int v, int dist){
this.v = v;
this.dist = dist;
}

@Override
public int compareTo(Node that) {
return this.dist - that.dist;
}
}

public int networkDelayTime(int[][] times, int N, int K) {

int n = times.length;
List<Edge>[] graph = new ArrayList[N];

for (int i = 0; i < N; ++i) {
graph[i] = new ArrayList<>();
}

for (int i = 0; i < n; ++i) {
int from   = times[i][0];
int to     = times[i][1];
int weight = times[i][2];
from --;
to --;
}

int ans = 0;
boolean[] vis = new boolean[N];

Queue<Node> queue = new PriorityQueue<>();
queue.offer(new Node(K - 1, 0));

int[] dist = new int[N];
Arrays.fill(dist, 0x3f3f3f3f);

while (!queue.isEmpty()) {
Node now = queue.poll();
for (Edge e : graph[now.v]) {
if (!vis[e.from]) {
Node nxt = new Node(e.to, now.dist + e.weight);
dist[e.to] = Math.min(dist[e.to], nxt.dist);
queue.offer(nxt);
}
}
vis[now.v] = true;
}

for (int i = 0; i < N; ++i) {
if (i == K - 1) continue;
ans = Math.max(ans, dist[i]);
}

return ans >= 0x3f3f3f3f ? -1 : ans;
}```

```     public int networkDelayTime(int[][] times, int N, int K) {
int INF = 0x3f3f3f3f;
int[][] dist = new int[N][N];

for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
dist[i][j] = INF;
}
}

for (int[] time : times) {
int from = time[0];
int to   = time[1];
int cost = time[2];
from --;
to --;
dist[from][to] = cost;
}

for (int k = 0; k < N; ++k) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}

int ans = 0;
for (int i = 0; i < N; ++i) {
if (i ==  K - 1) continue;
ans = Math.max(ans, dist[K - 1][i]);
}

return ans >= INF ? -1 : ans;
}```

warshallFloyd算法的正确性详见知乎高票回答【Floyd算法为什么把k放在最外层？

Python版：

```    def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
INF = 0x3f3f3f3f
dist = [[INF] * N for _ in range(N)]

for time in times:
u = time[0]
v = time[1]
w = time[2]
dist[u - 1][v - 1] = w

for k in xrange(N):
for i in xrange(N):
for j in xrange(N):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = 0
for i in range(N):
if (i == K - 1): continue
else:
ans = max(ans, dist[K - 1][i])

return -1 if ans >= INF else ans```

Python Dijkstra 版：

```    def networkDelayTime(self, times, N, K):
import heapq

"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
pq = []
INF = float('inf')
dist = [INF] * N

graph = [[] for _ in range(N)]

for time in times:
graph[time[0] - 1].append((time[1] - 1, time[2]))

heapq.heappush(pq, (0, K - 1))
dist[K - 1] = 0

while len(pq):
cur = heapq.heappop(pq)
for to, cost in graph[cur[1]]:
if (dist[to] > dist[cur[1]] + cost):
dist[to] = cost + dist[cur[1]]
heapq.heappush(pq, (dist[to], to))

ans = 0
for i in range(N):
if i == K - 1:
continue
else:
ans = max(ans, dist[i])

return -1 if ans >= INF else ans```

0 条评论

相关文章

2616

1023

2063

3110 二叉堆练习3

3110 二叉堆练习3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 给定N...

2825

26:统计满足条件的4位数个数

26:统计满足条件的4位数个数 总时间限制: 1000ms 内存限制: 65536kB描述 给定若干个四位数，求出其中满足以下条件的数的个数：  个位数上的...

4034

Numpy基础知识点汇总

1、概述 Numpy是高性能科学计算和数据分析的基础包，它的部分功能如下： 1）ndarray,一个具有矢量算术运算和复杂广播能力的快速且节省空间的多维数组。 ...

2904

1103

1714

1324