← All solutions

Shortest judge solution: 1712 bytes. Shortest team solution (during contest): 1870 bytes.

First, we need to figure out which streets can possibly be used (and in which direction), i.e., those which are part of some shortest path to the downtown node. This is standard and can be done by running Dijkstra’s algorithm from the downtown node. Writing d(u) for the distance from the downtown for intersection u, an edge (u, v, t) can be used from u to t if and only if d(u) = d(v) + t.

Checking this for all edges gives a directed acyclic graph consisting of all edges that can be used by the commuters. Next, we observe that two commuters that are at two nodes that have a different distance to downtown can never interfere with each other. This means that we can group the commuter based on their distance to downtown, and process each group separately.

Processing such a group of commuters is again a fairly standard task, namely finding edge-disjoint paths. Add a dummy node s and connect it to all the starting nodes of the commuters in the group (with multiplicities, so you allow parallel edges). Then, the maximum number of commuters that can go simultaneously within this group equals the maximum number of edge-disjoint paths from s to downtown, which equals the max-flow from s to downtown if you put unit capacities on all the (directed) edges.