+1 vote
65 views

# Siruseri Traffic Lights

In Siruseri, there are junctions connected by roads. There is at most one road between any pair of junctions. There is no road connecting a junction to itself. The travel time for a road is the same in both directions.

At every junction there is a single traffic light. These traffic lights are a bit peculiar. Starting from time 0, each light flashes green once every T time units, where the value of T is different for each junction.

A vehicle that is at a junction can start moving along a road only when the light at the current junction flashes green. If a vehicle arrives at a junction between green flashes, it must wait for the next green flash before continuing in any direction. If it arrives at a junction at exactly the same time that the light flashes green, it can immediatly proceed along any road originating from that junction.

You are given a city map that shows travel times for all roads. For each junction i, you are given Ti, the time period between green flashes of the light at that junction. 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.

## Solution hint

Use Dijkstra's algorithm. At 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.

## Input Format

There are N junctions and M roads. The junctions are identified by integers 1 through N.

• The first line of input contains two integers: the source junction and the destination junction.
• The second line contains two integers: N and M.
• The third line contains N integers, T1, T2,…TN, describing the time periods at which the traffic lights flash green. The light at junction i flashes green at times 0, Ti, 2Ti, 3Ti, …
• The next M lines contain information about the M roads. Each line has three integers ijlij , where:
• i and j are the junctions connected by this road
• lij is the time required to move from junction i to junction j using this road

## Output Format

A single line consisting of a single integer, the time taken by a minimum-time path from source to destination.

## Constraints:

• 2 ≤ N ≤ 300
• 1 ≤ M ≤ 14,000
• 1 ≤ T_i ≤ 100
• 1 ≤ lij ≤ 100

## Sample Input

1 4
4 5
4 3 2 5
1 2 4
1 3 8
2 3 6
2 4 10
3 4 7


## Sample Output

15


## Explanation

• 1 to 2 to 4 takes time 4 + 2 (wait till 6) + 10 = 16.
• 1 to 3 to 4 takes time 8 + 0 (no wait) + 7 = 15.
• 1 to 2 to 3 to 4 takes time 4 + 2 (wait for 6) + 6 + 0 (no wait) + 7 = 19.
• 1 to 3 to 2 to 4 takes time 8 + 0 (no wait) + 6 + 1 (wait till 15) + 10 = 25.
| 65 views

This problem can be solved by using Dijkstra’s algorithm, only the strategy to update the distance will be different.

Assume that you are leaving vertex $CURR$  at time (weight) $WT$.

Now, for any neighbor $V$ of $CURR$  the time required to reach $V$ will be $WT + \text{(time required to travel edge CURR-V)}$, lets call this time $D$

If $V$ is the destination, then you have a possible answer, but if $V$ is not destination, then you can leave from vertex $V$ only after some $x*T_V$ time, i.e. a multiple of $T_V$ which is greater than or equal to $D$, hence the new weight (or time) for $V$ will be $T_V*\lceil \frac{D}{T_V} \rceil$. Hence for each unvisited neighbor, calculate $D$ using above procedure and update the distance if $D$ is less than the stored distance.

This can be done efficiently by using set in C++ STL to implement priority queue.

Time complexity of the above approach will be $O(M*log N)$. Here’s a well commented C++ implementation for the same.

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9,maxN=301;
#define weight first
#define node  second

/*
Notations
G[i]: Adjacency list for i, contains {weight,node} pairs
G[i][j].node: Node to which vertex i is conncted
G[i][j].weight: weight of edge i-G[i][j].node
T[i]: Time period for i, as mentioned in problem statement
dist[i]: Distance of i-th vertex from source
vis[i]: 1 if vertex i is visited else 0
*/

vector < pair <int,int> > G[maxN];
int T[maxN],dist[maxN],vis[maxN];

int dijkstra(int src,int dst,int n)
{
set < pair <int,int> > pq;	//priority queue
for(int i=1;i<=n;++i)
{
if(i!=src) dist[i]=inf;	//initial distance is infinite
}

//Dijkstra's Algorithm
while(!pq.empty())
{
auto top=*pq.begin();		//get top element
pq.erase(pq.begin());		//delete top element
int wt=top.weight,curr=top.node;
vis[curr]=1;			//mark as visited

if(wt==inf) break;		//No path is possible

//update weights for unvisited nodes connected to current node
for(auto p:G[curr]) if(!vis[p.node])
{
int v=p.node;
int d=wt+p.weight;	//time to reach v

//time at which the next path can be used
if(v!=dst) d=T[v]*((d+T[v]-1)/T[v]);

//if new distance is less than stored distance
//then update the distance of v as new distance
if(d<dist[v])
{
pq.erase(pq.find({dist[v],v}));
dist[v]=d;
pq.insert({dist[v],v});
}
}
}

return dist[dst];	   //return distance of destination
//inf will be returned if the destination is not reachable
}

int main()
{
int N,M,src,dst;
cin>>src>>dst;
cin>>N>>M;

//input time periods
for(int i=1;i<=N;++i) cin>>T[i];

//input edges and update adjacency lists
while(M--)
{
int i,j,lij;
cin>>i>>j>>lij;
G[i].push_back({lij,j});
G[j].push_back({lij,i});
}

cout<<dijkstra(src,dst,N);	//calculate and display result
return 0;
}

P.S. Since the constraint for $N$ is small, you can also use $O(N^2)$ implementation of Dijkstra's Algorithm. You can read more about it here. But you will still need to update the weights using the above mentioned strategy.

by (855 points)
edited
0

Bro, I encountered same question on codechef editorial here, it had like $O(N^2)$ complexity.

Your’s is $O(M * log N)$ so, your’s far better than sparse graph.

0
👍 Correct
0
Thanks