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.

- After
`1`

unit of time, the signal will reach the city`3`

- After
`2`

units of time the signal will reach the city`2`

- 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"; }