P6512 [QkOI#R1] Quark and Flying Pigs

You are given a simple, connected, undirected weighted graph with $n$ vertices and $m$ edges. At time $0$, you are at vertex $1$. Suppose the current time is $t$ and you are at vertex $v$. You may choose one of the following operations: - Stay at vertex $v$. After the operation, the time becomes $t+1$. - Choose an edge $(a,b,w)$ such that $a=v$ or $b=v$. Then you move to the other endpoint of this edge. After the operation, the time becomes $t+w$. There are $k$ pieces of information. Each piece is of the form $(t_i,v_i)$, meaning that at time $t_i$, a flying pig with ID $i$ will appear at vertex $v_i$. If you are at $v_i$ at that time, then you capture flying pig $i$. Now you need to find the maximum number of flying pigs you can capture.

The first line contains three positive integers $n,m,k$. The next $m$ lines each contain three positive integers $a_i,b_i,w_i$. The next $k$ lines each contain two positive integers $t_i,v_i$.

Output one integer in a single line: the maximum number of flying pigs you can capture.

### Sample Explanation The optimal plan is as follows: At time $0$, choose to move to node $2$, and the time becomes $2$. At time $2$, capture the $2$-nd flying pig, choose to stay at node $2$, and the time becomes $3$. At time $3$, capture the $3$-rd flying pig, choose to move to node $1$, and the time becomes $5$. At time $5$, capture the $4$-th flying pig, choose to move to node $2$, and the time becomes $7$. At time $7$, capture the $5$-th flying pig. ### Constraints For $20\%$ of the testdata, $n,m,k\le 7$. For $100\%$ of the testdata, $2\le n\le 200$, $1\le m\le \frac{n(n-1)}{2}$, $1\le k\le 5000$, $1\le a_i,b_i,v_i\le n$, $1\le w_i\le 1000$, $1\le t_i\le 10^9$. Translated by ChatGPT 5