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 \leq K \leq N$），第 $i$ 个干草堆的美味度为 $y_i$。每头奶牛愿意在去牛棚的途中停在一个干草堆处进食，但前提是：这会给她的路径增加的时间不超过她所拜访的干草堆的美味度。注意，一头奶牛在“正式”用餐意义上最多只会拜访一个干草堆，尽管她的路径可以经过其他也有干草堆的牧场；她会忽略这些干草堆。

输入格式

第一行包含三个用空格分隔的整数 $N$、$M$ 和 $K$。 接下来 $M$ 行每行包含三个整数 $a_i$、$b_i$ 和 $t_i$，描述一条连接牧场 $a_i$ 与 $b_i$ 的小路，穿过它需要 $t_i$ 时间（$a_i$ 与 $b_i$ 彼此不同，且 $t_i$ 为不超过 $10^4$ 的正整数）。 接下来 $K$ 行每行用两个整数描述一个干草堆：所在牧场的编号，以及其美味度（不超过 $10^9$ 的正整数）。 同一个牧场中可以有多个干草堆。

输出格式

输出应包含 $N-1$ 行。第 $i$ 行输出一个整数：如果位于牧场 $i$ 的奶牛可以在去牛棚的路上拜访并享用某个干草堆，则输出 $1$，否则输出 $0$。

4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7

1
1
1

提示

在这个例子中，牧场 3 的奶牛应该停下来吃一顿，因为她的路线长度只会增加 6（从 2 增加到 8），且这个增加量不超过干草堆的美味度 7。牧场 2 的奶牛显然应该吃牧场 2 的干草，因为这不会改变她的最优路线。牧场 1 的奶牛是一个有趣的情况，因为乍一看她的最优路线（长度 10）似乎会因停下吃草而增加太多，不值得这么做。然而，她实际上确实存在一条路线使得停下来吃草是有利的：先到牧场 4，再到牧场 2（吃草），然后回到牧场 4。 题目鸣谢：Dhruv Rohatgi

标签: USACO|2018|Gold

来源

USACO|2018|Gold