Shortcut

题目描述

每天傍晚，农夫 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，前提是两者总通行时间相同）。 农夫 John 担心有些田地离牛棚太远。他把每头奶牛所经历的通行时间加总（对所有奶牛求和），称为总通行时间。他希望通过额外添加一条“捷径”小路来尽可能减少这个数：这条捷径从牛棚（1 号田地）连接到他选定的某块田地，通行时间为 $T$（$1 \leq T \leq 10,000$）。如果奶牛在沿着她平时前往牛棚的路径行走时遇到了这条捷径小路，并且走捷径能让她更快到达牛棚，那么她就会走捷径。否则，奶牛仍会按她原本的路线行走，即使存在使用捷径来改善时间的可能。 请帮助农夫 John 确定：通过添加这条捷径小路，他能够使总通行时间减少的最大值。

输入格式

第一行包含 $N$、$M$ 和 $T$。 下一行包含 $N$ 个整数 $c_1 \ldots c_N$，每个都在范围 $0 \ldots 10,000$。 接下来 $M$ 行每行用三个整数 $a$、$b$、$t$ 描述一条小路，表示该小路连接田地 $a$ 与 $b$，通行时间为 $t$。所有通行时间都在范围 $1 \ldots 25,000$。

输出格式

请输出农夫 John 通过添加捷径小路所能实现的总通行时间的最大减少量。

5 6 2
1 2 3 4 5
1 2 5
1 3 3
2 4 3
3 4 5
4 5 2
3 5 7

40

提示

题目来源：Brian Dean

标签: USACO|2019|Gold

来源

USACO|2019|Gold