INLO33 - Editorial

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:

//