Project 4: Shortest Paths

The city has setup a radio station to broadcast the current traffic situation to all the cars moving in the city. So the cars now intelligently choose the shortest path to their destination by considering the current traffic situation.

At each station, the car decides it's next hop based on it's current shortest path to the destination. The shortest path is computed by taking into account the current traffic situation.

At any instant, if cars are getting off the road (leaving an edge) and getting on the road at the same time, use the following ordering:
  1. All cars first get off the road.
  2. Then, shortest paths get computed.
  3. Then cars start getting on to the road.
This means that if two cars are starting on an edge simultaneously, they will not count as traffic for each other while computing the shortest path. But, one will count as traffic for the other (car with smaller ID number will count as traffic for the car with the larger ID number) while computing the time spent on the road.

Everything else is the same as that in Project 3. In the input, you will now no longer be given the next-hop matrix.

Support files:
  1. Sample input
  2. Sample output (does not correspond to sample input, just tells you the syntax).
  3. Another sample input