USACO 2018 Dec Gold

1. Fine Dining

备注

漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。

农场由 $N$ 片牧场组成（$2 \leq N \leq 50,000$），方便起见编号为 $1 \dots N$。所有奶牛都要前往位于牧场 $N$ 的牛棚。其他 $N-1$ 片牧场中每片有一头奶牛。奶牛们可以通过 $M$ 条无向的小路在牧场之间移动（$1 \leq M \leq 100,000$）。第 $i$ 条小路连接牧场 $a_i$ 和 $b_i$，通过需要时间 $t_i$ 。每头奶牛都可以经过一些小路回到牛棚。

由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有 $K$ 个有美味的干草捆 $(1\le K \le N)$，第 $i$ 个干草捆的美味值为 $y_i$。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅“正式地”在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。

分层图模型

将未进食的状态视为一层，进食后的状态视为另一层。如果某个牧场有干草，则意味者可以在该节点从未进食状态转为进食状态。这种转化只能进行一次。

本题需要求所有节点到 $n$ 的最短路。因此，我们求反图中 $n$ 到其他节点的最短路。

具体实现如下： 因为是反着处理，所以下面的过程与实际的过程是相反的。

用 $f(i)$ 表示从 $n$ 走到 $i$，不进行觅食的最短路。该数组可通过 dijkstra 算法求得。

用 $g(i)$ 表示从 $n$ 走到 $i$，且进行过一次觅食的最短路。

初使条件：若 $k$ 是牧场，则 $g(k) = f(k)$，否则 $g(k) = f(k) - y_k$。

接下来正常进行转移即可。

最后，若 $g(i) \le f(i)$，则意味着牧场 $i$ 的奶牛可通过一次觅食，不会使得路程变大。应输出 $1$。