P5201 [USACO19JAN] Shortcut G

USACO 19 年一月月赛金组第三题

每天晚上，Farmer John 都会敲响一个巨大的铃铛，召唤他的奶牛们前来牛棚享用晚餐。奶牛们都急切地想要前往牛棚，所以她们都会沿着最短的路径行走。 农场可以描述为 $N$ 块草地（$1 \leq N \leq 10,000$），方便起见编号为 $1 \ldots N$，牛棚位于草地 $1$。草地之间由 $M$ 条双向的小路连接（$N-1 \leq M \leq 50,000$）。每条小路有其通过时间，从每块草地出发都存在一条由一些小路组成的路径可以到达牛棚。 草地 $i$ 中有 $c_i$ 头奶牛。当她们听到晚餐铃时，这些奶牛都沿着一条消耗最少时间的路径前往牛棚。如果有多条路径并列消耗时间最少，奶牛们会选择其中“字典序”最小的路径（也就是说，她们通过在两条路径第一次出现分支的位置优先选择经过编号较小的草地的方式来打破并列关系，所以经过草地 $7$、$3$、$6$、$1$ 的路径会优先于经过 $7$、$5$、$1$ 的路径，如果它们所消耗的时间相同）。 Farmer John 担心牛棚距离某些草地太远。他计算了每头奶牛路上的时间，将所有奶牛消耗的时间相加，称这个和为总移动时间。他想要通过额外添加一条从牛棚（草地 $1$）连接到某块他选择的其他草地的、通过时间为 $T$（$1 \leq T \leq 10,000$）的“近道”来尽可能地减少总移动时间。当一头奶牛在她平时前往牛棚的路上偶然看见这条近道时，如果这条近道能够使她更快地到达牛棚，她就会走这条路。否则，一头奶牛会仍然沿着原来的路径行走，即使使用这条近道可能会减少她的移动时间。 请帮助 Farmer John 求出通过添加一条近道能够达到的总移动时间减少量的最大值。

无

无