P5201 [USACO19JAN] Shortcut G

The third Gold problem of the USACO January 2019 contest.

Every evening, Farmer John rings a huge bell to call his cows to the barn for dinner. The cows are eager to get to the barn, so they all travel along the shortest path. The farm can be described as $N$ fields ($1 \leq N \leq 10,000$), numbered $1 \ldots N$ for convenience, and the barn is located at field $1$. The fields are connected by $M$ bidirectional paths ($N-1 \leq M \leq 50,000$). Each path has a travel time, and from every field there exists a route (made of some paths) that can reach the barn. Field $i$ has $c_i$ cows. When they hear the dinner bell, these cows all head to the barn along a path with the minimum total travel time. If multiple paths tie for the minimum total time, the cows choose the lexicographically smallest path (that is, they break ties by, at the first point where the two paths diverge, preferring the one that goes through the smaller-numbered field. So the path through fields $7$, $3$, $6$, $1$ is preferred over the path through $7$, $5$, $1$ if they take the same amount of time). Farmer John worries that the barn is too far from some fields. He computes the travel time for each cow and sums them up, calling this sum the total travel time. He wants to reduce the total travel time as much as possible by adding one extra “shortcut”: a path from the barn (field $1$) to some other field of his choice, with travel time $T$ ($1 \leq T \leq 10,000$). When a cow happens to see this shortcut while traveling to the barn along her usual route, if taking the shortcut would allow her to reach the barn faster, she will take it. Otherwise, she will still follow the original route, even if using the shortcut might reduce her travel time. Help Farmer John find the maximum possible reduction in total travel time that can be achieved by adding one shortcut.

The first line contains $N$, $M$, and $T$. The next $N$ lines contain $c_1 \ldots c_N$, each an integer in the range $0 \ldots 10,000$. The next $M$ lines each contain three integers $a$, $b$, and $t$, describing a path connecting fields $a$ and $b with travel time $t$. All travel times are in the range $1 \ldots 25,000$.

Output the maximum reduction in total travel time that Farmer John can achieve.

Translated by ChatGPT 5