+1-5714784200

Similar Problems

Similar Problems not available

Signal delay time - Leetcode Solution

Companies:

LeetCode:  Signal delay time Leetcode Solution

Difficulty: Unknown

Topics: graphs  

There are N cities labelled from 1 to N . We want to send a signal from a city K . The amount of time it takes for the signal to travel from one city to another city is also given in the array Times . Output the integer t , which is the minimum time taken by the signal to reach all the cities. If the signal cannot reach even one city, output -1 .

Example Test Cases

Sample Test Case 1

N: 4
Times:

  • 1, 2, 2
  • 1, 3, 1
  • 2, 4, 6
  • 3, 4, 3

K: 1
Expected Output: 4

Explanation: We can represent the above test case with the following image.

  1. After 1 unit of time, the signal will reach the city 3
  2. After 2 units of time the signal will reach the city 2
  3. After 4 units of time, the signal will reach the city 4

Therefore, the minimum time taken to reach all the cities is 4 , which is the answer to the test case.

Solution

We can easily represent this problem using a graph where each city will correspond to one node. If city B is reachable from city A , there will be a directed edge from A to B with edge weight equal to the time taken to reach city B

The minimum amount of time taken to reach a particular city i from city k is the minimum distance of city i from city k . Therefore, assuming that all the cities are reachable, the minimum amount of time it takes to reach all the cities will the time taken to reach the farthest city. This is a classic case of Single source shortest path algorithm and can be solved using Dijkstra’s algorithm. Take a look at the code below:

Signal delay time Solution Code

1