# Signal delay time

Companies:

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:

#### Implementation

```#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// Implementation of Dijkstra's algorithm algorithm.
vector<int> computeDistance(vector<vector<pair<int, int>>>& graph, int k) {
// dist stores the distance to each node.
vector<int> dist(graph.size());
// Initializing the distance array to inifinity (INT_MAX) as every node is not reachable initially.
for(int i = 0; i < dist.size(); i++) dist[i] = INT_MAX;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(k, 0));
while (!pq.empty()) {
int currentDistance = pq.top().second;
int top = pq.top().first;
pq.pop();
if (dist[top] > currentDistance) {
dist[top] = currentDistance;
for(int i = 0; i < graph[top].size(); i++) {
int v = graph[top][i].first;
int w = graph[top][i].second;
if (dist[v] > currentDistance + w) {
pq.push(make_pair(v, currentDistance + w));
}
}
}
}
return dist;
}

vector<int> addEdge(int u, int v, int w) {
vector<int> vec;
vec.push_back(u);
vec.push_back(v);
vec.push_back(w);
return vec;
}

int main() {
int N = 4;
int k = 1;
vector<vector<int>> times;
times.push_back(addEdge(1, 2, 2));
times.push_back(addEdge(1, 3, 1));
times.push_back(addEdge(2, 4, 6));
times.push_back(addEdge(3, 4, 3));

vector<vector<pair<int, int>>> graph(N);

for(int i = 0; i < times.size(); i++) {
vector<int> edge = times[i];
int u = edge[0] - 1, v = edge[1] - 1, w = edge[2];
graph[u].push_back(make_pair(v, w));
}

vector<int> distance = computeDistance(graph, k - 1);
int ma = INT_MIN;
for(int i = 0; i < distance.size(); i++) ma = max(ma, distance[i]);
if (ma == INT_MAX) cout << "-1\n";
else cout << ma << "\n";
}```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.