Question

You are given a roadmap of a country consisting of N cities and M roads. Each city 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 seconds 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. For each nodex, find the number of routes that will take the minimum amount of time (in seconds) required to move from city 1 to dty N passing through that city x It is guaranteed that the given roadmap will be connected. Graph won't contain multiple edges and self-loops. Input Format The first line contains 4 space-separated integers, N(1 N 109) M(N-1M <(N(N-172) T(1 T <10) and C(1 oC 103. Next M lines contain two integers each, U and V denoting that there is a bidirectional road between U and V. Output Format Print Nintegers, where ith denotes the number of routes which will take the minimum amount of time (in seconds) required to move from city 1 to city N passin through that city! Problem Statement You are given a roadmap of a country consisting of N cities and M roads. Each city 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 seconds. 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 to city N. It is guaranteed that the given roadmap will be connected. Graph wont contain multiple edges and self loops. Input Format The first line contains 4 space-separated integers, N (1<=N<-10), M(N-1 MC=(N(N-1/2). T(1 <=T<=10) and c(1oC6103). Next M lines contain two integers each. U and V denoting that there is a bidirectional road between U and V. Output Format Print the minimum amount of time (in seconds) required to move from city 1 to city N. Problem Statement You are given a roadmap of a country consisting of N cities and M roads. Each city 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 seconds. 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 seconds Find the second minimum amount of time in seconds) required to move from city 1 to city N. You can go through a city only once. It is guaranteed that the given roadmap will be connected. Graph wont contain multiple edges and self-loops. Input Format The first line contains 4 space-separated integers, N(N 100 MIN-1 MC (N-1821. Tf1 T610and C11 C10). Next Mines contain two Integers each U and V denoting that there is a bidirectional road between U and V. Output Format Print the second minimum amount of time (in seconds required to move from city 1 to dryIf the second minimum time does not exist print -1. Sample Testcase #0​

Answer 1

Answer:

I have got the answer but with the worst time complexity bruteforce method ,I just have to find the better way to calculate the shortest distance.

Answer 2

Explanation:

The Fastest path will be 1->2-> 5.

One can reach city 2 in 5 seconds.

After 3 seconds the traffic light in city 2 will turn Red.

So in city 2. one has to wait for 1 second for the traffic light to turn Green.

So total time will be 5 seconds (from city 1 to city 2) + 1 second (waiting time at city 2) + 5 seconds (from city 2 to city 5) = 11 seconds.

Because all the cities start with the same initial state, switch lights with the same frequency, and all the roads have the same duration, the traffic lights delay all routes equally.

As all roads have the same duration, this means that BFS will be an efficient way to solve the problem.

The only adjustment to the standard algorithm is to adjust the time at each node to account for any delay due to the traffic lights.

If the roads had different durations, or the lights switched irregularly, then a more advanced algorithm such as Dijkstra would be required.