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.

Awesome q2a theme

+1 vote

*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.

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.

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*, 2*Ti*, 3*Ti, …* - The next
*M*lines contain information about the*M*roads. Each line has three integers*i*,*j*,*lij*, 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

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

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

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

15

- 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.

+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.

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.

8,446 questions

2,720 answers

13,274 comments

95,468 users