Awesome q2a theme
+1 vote
65 views

Siruseri Traffic Lights

Adapted from Traffic Lights, International Olympiad in Informatics, 1999

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.
in Graph Theory by (9 points) | 65 views

1 Answer

+5 votes

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
		pq.insert({dist[i],i});	//add i to pq
	}

	//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 by
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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,446 questions
2,720 answers
13,274 comments
95,469 users