Question

Problem Statement You are given a roadmap of a country consisting of N cities and M roads. Each cit has a traffic light. The traffic light has only 2 colors, Green and Red. All the traffic lights will switch their color from Green to Red and vice versa after every T secon You can cross a city only when the traffic light in the city is Green. Initially, all the traffic lights are Green. At a city, if the traffic light is Red, you have to wait for it to switch its color to Green. The time taken to travel through any road is C seconds. Find the minimum amount of time (in seconds) required to move from city 1 toc N. It is guaranteed that the given roadmap will be connected. Graph won't contain multiple edges and self loops. Input Format​

Answer 1

Answer:We are given a country, having N cities and M bidirectional roads. Each city has a traffic light, showing only 2 colors i.e Green and Red. All the traffic lights switch their color from Green to Red or vice versa after every T seconds. We can cross a city only when the traffic light is green. Initially, all traffic light is green. In any city, if the traffic light is Red then we have to wait for its light to turn green. Time taken to travel any road is C. We have to find minimum time to reach City N from 1.

Note: graph doesn't contain a self-loop or multiple edges.

For example:

N=5,M=5,T=3,C=5

Edges are:

1 2,

1 3,

2 4,

1 4,

2 5.

Here minimum time to go from 1 to 5 is 11 through path 1 2 5.WE can reach city 2 in 5 secs. then wait for 1 second for the light to turn green and then 5 seconds to go to 5.

Explanation: