P2934 [USACO09JAN] Safe Travel G

Gremlins have infested the farm. These nasty, ugly fairy-like creatures thwart the cows as each one walks from the barn (conveniently located at pasture\_1) to the other fields, with cow\_i traveling to from pasture\_1 to pasture\_i. Each gremlin is personalized and knows the quickest path that cow\_i normally takes to pasture\_i. Gremlin\_i waits for cow\_i in the middle of the final cowpath of the quickest route to pasture\_i, hoping to harass cow\_i. Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly different route from pasture\_1 (the barn) to pasture\_i. Compute the best time to traverse each of these new not-quite-quickest routes that enable each cow\_i that avoid gremlin\_i who is located on the final cowpath of the quickest route from pasture\_1 to pasture\_i. As usual, the M (2 2 p_1 to p_3 1->2->3 3 1->3 p_1 to p_4 1->3->4 6 2->4 ``` For 20% of the test data, N

N/A

N/A