Network Delay Time · Interview Problem

Back to problems

Leetcode

network-delay-time

Medium

Graphs

Shortest Path

Dijkstra's Algorithm

Heap (Priority Queue)

Network Delay Time

Given a list of travel times as directed edges, determine the time it will take for all nodes to receive a signal sent from a given starting node.

Acceptance 100%

Start Practice Editorial

Problem Statement

Core description from the backend problem record.

Description

You are given a network of n nodes, labeled from 1 to n. You are also 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 u to v. You send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the nodes to receive the signal, return -1.

Input Format

n: integer, the number of nodes in the network
times: list of tuples (u, v, w) representing directed edges and travel times
k: integer, the starting node from which the signal is sent

Output Format

Integer representing the time it takes for all nodes to receive the signal or -1 if impossible.

Constraints

1 <= n <= 100
1 <= times.length <= 6000
1 <= u, v <= n
0 <= w <= 100
All edges are directed and may not necessarily connect all nodes

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 4, times = [[2,1,1],[2,3,1],[3,4,1]], k = 2

Output

Explanation

Starting from node 2, the signal reaches node 1 in 1 unit, node 3 in 1 unit, and then node 4 in 2 units. The maximum time to reach all nodes is 2.

Loading Preptin

Description

Input Format

Output Format

Constraints