USACO 2018 - Dec - Gold - Fine Dining

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=861
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đàn bò đang trở về chuồng sau một ngày dài mệt mỏi.

Trang trại có ~N~ đồng cỏ, được đánh số ~1...N~. Chuồng bò đặt tại đồng cỏ ~N~. Trong ~N - 1~ đồng cỏ còn lại, mỗi đồng cỏ đều có một chú bò. Các chú bò sẽ trở về chuồng thông qua ~M~ con đường hai chiều nối các đồng cỏ. Con đường thứ ~i~ kết nối đồng cỏ ~a_{i}~ với đồng cỏ ~b_{i}~ và tốn ~t_{i}~ thời gian để đi qua. Mỗi chú bò đều có thể trở về chuồng thông qua một chuỗi các con đường.

Ngoài ra, trang trại có những bó cỏ khô đặt tại ~K~ đồng cỏ phân biệt. Các chù bò rất đói nên muốn được ăn cỏ khô trên đường về chuồng. Gọi thời gian ít nhất để một chú bò về chuồng là ~S~, thời gian ít nhất để ăn được bó cỏ khô tại cánh đồng thứ ~i~ và về chuồng là ~T~, độ ngon của bó cỏ tại cánh đồng thứ ~i~ là ~y_i~, chú bò này chỉ ăn bó cỏ khô tại cánh đồng thứ ~i~ khi và chỉ khi ~T - S \le y_i~. Lưu ý mỗi chú bò chỉ ăn bó cỏ khô tại một cánh đồng, dù trên đường về chuồng chú bò ấy có thể đi qua nhiều cánh đồng có bó cỏ khô.

Hãy đếm số chú bò ăn được cỏ khô khi đi theo các con đường tối ưu.

Input

  • Dòng đầu chứa 3 số nguyên dương ~N~, ~M~ và ~K~ ~(2 \le N \le 5 \cdot 10^4, 1 \le M \le 10^5, 1 \le K \le N)~ lần lượt là số đồng cỏ, số con đường và số đồng cỏ chứa các bó cỏ khô.

  • ~M~ dòng tiếp theo, dòng thứ ~i~ chứa 3 số nguyên dương ~a_{i}, b_{i}, t_{i}~ được mô tả theo đề bài ~(1 \le a_i, b_i \le N, a_i \ne b_i, 1 \le t_i \le 10^4)~.

  • ~K~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên dương ~x_i~ và ~y_i~ ~(1 \le x \le N, 1 \le y_i \le 10^9)~ lần lượt là đồng cỏ có bó cỏ khô thứ ~i~ và độ ngon của bó cỏ đó.

Output

  • Ghi ra ~N - 1~ dòng, dòng thứ ~i~ là ~1~ nếu chú bò ở đồng cỏ ~i~ có thể ăn được cỏ khô trên đường về chuồng và ~0~ nếu ngược lại.

Sample Input

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

Sample Output

1
1
1

Giải thích

  • Chú bò ở đồng cỏ ~3~ có thể đến và ăn cỏ ở đồng cỏ ~2~ rồi đến đồng cỏ ~4~, mất ~5 + 3 = 8~ đơn vị thời gian. Trong khi ở phương án tối ưu, chú bò đi từ đồng cỏ ~3~ đến ~4~ mất ~2~ đơn vị thời gian. Vì độ chênh lệch là ~8 - 2 = 6 \le 7~ nên chú bò ăn được cỏ.

  • Chú bò ở đồng cỏ ~2~ chỉ cần ăn bó cỏ khô tại chính đồng cỏ ~2~.

  • Chú bò ở đồng cỏ ~1~ có thể đến đồng cỏ ~4~ rồi đến đồng cỏ ~2~ ăn cỏ, sau đó lại quay về chuồng ở đồng cỏ ~4~. Độ chênh lệch thời gian là ~6~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.