Stoplight Traveling Salesman

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

You are given a graph with costs on edges representing the time to traverse them in seconds. However, each edge also has associated with it one of k colors and edges of a each color c have two associated numbers in units of seconds greentime_c and redtime_c. Starting at time 0, the edge is passable during the first greentime_c seconds, then unpassable during the next redtime_c seconds, then passable for the next greentime_c seconds, then unpassable during the next redtime_c seconds, etc. If the edge has say 10 seconds remaining of its passable time and the time to traverse is 12 seconds, you may not traverse it nor stay in the middle (think of this as a traffic intersection). So if you start to traverse an edge, you must start in a green period and finish the traversal still in a green period with a green period throughout.

There will be approximately 200 nodes and 10000 edges and at most 10 colors. All edges are bi-directional.

The data will come in two tables.
node1 node2 color traversetime
color greentime redtime

Both will be in a single file. Here is a typical file.

You want to find the shortest time to visit all nodes reachable from a given starting node.

Your output should simply give a sequence of edges taken and when the edge traversal begins and ends. So everyone will be given the same graph. The winner(s) will find a shortest path on all nodes taking into account redtimes and greentimes and of course traverse times.

Architecture Team

You will be given the stoplight file on the day of the competition (which may have more or fewer colors but no more than 10 and no more than 10000 edges). Show the route taken one edge per line. Check for violations of the above rules plus check that the total execution time doesn't exceed two minutes. Calculate the time (including stops) of the path suggested. Here is an implementation of a slightly different problem from 2017 Here is the zip file of the same code.