PROBLEM LINK:
Author: RAVIT SINGH MALIK
Editorialist: RAVIT SINGH MALIK
DIFFICULTY:
HARD
PREREQUISITES:
DIJKSTRA , GRAPHS
PROBLEM:
Your task is to find the minimum time taken from a given source junction to a given destination junction
for a vehicle when the traffic starts.
EXPLANATION:
This problem is completely based on Dijkstra’s algorithm,which is used for
finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
The algorithm exists in many variants; Dijkstra’s original variant found the shortest path
between two nodes, but a more common variant fixes a single node as the “source” node and
finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.
Pseudocode :
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // Initialization
6 dist[v] ← INFINITY // Unknown distance from source to v
7 prev[v] ← UNDEFINED // Previous node in optimal path from source
8 add v to Q // All nodes initially in Q (unvisited nodes)
9
10 dist[source] ← 0 // Distance from source to source
11
12 while Q is not empty:
13 u ← vertex in Q with min dist[u] // Source node will be selected first
14 remove u from Q
15
16 for each neighbor v of u: // where v is still in Q.
17 alt ← dist[u] + length(u, v)
18 if alt < dist[v]: // A shorter path to v has been found
19 dist[v] ← alt
20 prev[v] ← u
21
22 return dist[], prev[]
SO,the given question is a simple improvisation of Dijkstra’s algorithm, In which each phase, from the current shortest time for a given junction,
compute when the next green flash will occur to let you travel to its neighbours and
use this to update shortest path information.
CODE
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 1; v <= V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int dijkstra( int src)
{
int dist[V],f,x,c;
bool sptSet[V];
for (int i = 0; i <=V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V-1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 1; v <=V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX )
{
f=dist[u]+graph[u][v];
` c=f/T[v];
if(v==r)
x=dist[u]+graph[u][v];
else if(f%T[v]!=0)
x=(c+1)*T[v];
else
x=f;
if( x < dist[v])
dist[v] = x;
}
}
return dist[r];
}
===>> dist[r] is the required answer.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.