P6759 [USACO06OPEN] The County Fair

Every year, FJ likes to go to the county fair. There are $n$ booths at the fair, and each booth $i$ will give out an exquisite gift at a specific time $p_i$ on that day. FJ has heard about this and hopes to collect as many gifts as possible to share with his cows. To get the gift from booth $i$, FJ must make sure he is at booth $i$ exactly at time $p_i$. To collect as many gifts as possible, FJ did a detailed investigation. From this investigation, FJ determined the time $t_{i,j}$ it takes to travel from booth $i$ to booth $j$. The layout of the fair is very unusual, which means that if FJ chooses to detour via other booths while traveling from $i$ to $j$, it might take less time than going directly from $i$ to $j$. However, the straightforward FJ never does this: if he wants to go from booth $i$ to booth $j$, he will definitely spend $t_{i,j}$ time to walk from $i$ to $j$. In addition, because the fairground is rugged, $t_{i,j}$ may be different from $t_{j,i}$. FJ is at booth $1$ at time $0$. Please compute the maximum number of gifts he can collect.

Line $1$: An integer $n$, the number of booths. Lines $2$ to $n+1$: $n$ integers. The integer on line $i+1$ is $p_i$, the time when booth $i$ gives out its gift. Lines $n+2$ to $n^2+n+1$: $n^2$ lines. The first $n$ lines describe the time needed for FJ to walk from booth $1$ to booths $1$ to $n$ ($t_{1,1}, t_{1,2}, \ldots, t_{1,n}$). The next $n$ lines describe the time needed for FJ to walk from booth $2$ to booths $1$ to $n$ ($t_{2,1}, t_{2,2}, \ldots, t_{2,n}$), and so on. The last $n$ lines describe the time needed for FJ to walk from booth $n$ to booths $1$ to $n$ ($t_{n,1}, t_{n,2}, \ldots, t_{n,n}$). For any booth $i$, $t_{i,i}=0$.

One line: An integer, the maximum number of gifts FJ can collect.

#### Sample Explanation In the sample, there are $4$ booths at the fair. Booth $1$ gives out gifts at time $13$, booth $2$ at time $9$, booth $3$ at time $19$, and booth $4$ at time $3$. FJ first walks from booth $1$ to booth $4$, which takes $3$ time units, and arrives at time $3$, so he can get the gift. Then he walks from booth $4$ to booth $2$, which takes $5$ time units, and arrives at time $8$. After waiting for $1$ time unit, he can get the gift from booth $2$. Next he walks from booth $2$ to booth $1$, which takes $4$ time units, and arrives at time $13$, so he can collect the third gift. #### Constraints For $100\%$ of the testdata, $1\le n\le 400$, $0\le p_i\le 10^9$, $1\le t_{i,j}\le 10^6$. The testdata is from darkbzoj. Translated by ChatGPT 5