P5122 [USACO18DEC] Fine Dining G

After a long day, the hungry and tired cows are ready to return to the barn. The farm has $N$ pastures ($2\le N\le 5\times 10^4$), numbered $1\dots N$ for convenience. All cows want to go to the barn located at pasture $N$. Each of the other $N-1$ pastures has one cow. The cows can move between pastures using $M$ undirected paths ($1\le M\le 10^5$). The $i$-th path connects pastures $a_i$ and $b_i$, and it takes time $t_i$ to travel along it. Each cow can take some sequence of paths to get back to the barn. Because they are hungry, the cows are happy to stop and eat along the way home. There are $K$ pastures with tasty hay bales ($1 \le K \le N$). The $i$-th hay bale has tastiness value $y_i$. Each cow wants to stop at exactly one hay bale on her way to the barn, but she will do so only if going through that hay bale increases her travel time to the barn by no more than the hay bale’s tastiness value. Note that a cow only “officially” stops to eat at one hay bale, even if her path passes through other pastures that also have hay bales; she will simply ignore the other hay bales.

The first line contains three space-separated integers $N$, $M$, and $K$. The next $M$ lines each contain three integers $a_i$, $b_i$, and $t_i$, describing a path between pastures $a_i$ and $b_i$ that takes time $t_i$ to traverse ($a_i$ is not equal to $b_i$, and $t_i$ is a positive integer not exceeding $10^4$). The next $K$ lines each describe a hay bale with two integers: the index of the pasture where the hay bale is located, and its tastiness value (a positive integer not exceeding $10^9$). There may be multiple hay bales in the same pasture.

Output $N-1$ lines. If the cow in pasture $i$ can visit some hay bale and eat there on her way back to the barn, output an integer $1$ on line $i$; otherwise output an integer $0$.

In this example, the cow in pasture $3$ can stop to eat, because her time to get back increases by only $6$ (from $2$ to $8$), and this increase does not exceed the hay bale’s tastiness value $7$. The cow in pasture $2$ can clearly eat the hay in pasture $2$, since this does not cause her best path to change. The cow in pasture $1$ is an interesting case, because it looks like her best path ($10$) might increase too much if she goes to eat. However, there is indeed a path that lets her stop at a hay bale: first go to pasture $4$, then go to pasture $2$ (eat hay), and then return to pasture $4$. Translated by ChatGPT 5