P6005 [USACO20JAN] Time is Mooney G

Bessie is planning a business trip to Cow-nia, which has $N$ cities ($2 \leq N \leq 1000$) numbered $1 \ldots N$, connected by $M$ ($1 \leq M \leq 2000$) one-way roads. Each time Bessie visits city $i$, she can earn $m_i$ Mooney ($0 \leq m_i \leq 1000$). Starting from city $1$, Bessie wants to earn as much Mooney as possible and finally return to city $1$. To avoid disputes, $m_1=0$. Traveling along a road between two cities takes one day. Preparing for the trip is very expensive; traveling for $T$ days costs $C \times T^2$ Mooney ($1 \leq C \leq 1000$). What is the maximum amount of Mooney Bessie can earn in one trip? Note that the best plan might be that Bessie does not visit any city other than city $1$; in this case, the answer should be $0$.

The first line contains three integers $N$, $M$, and $C$. The second line contains $N$ integers $m_1,m_2,\ldots, m_N$. Each of the next $M$ lines contains two space-separated integers $a$ and $b$ ($a \neq b$), indicating a one-way road from city $a$ to city $b$.

Output one line containing the required answer.

The best travel plan is $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to1$. Bessie earns a total of $10+20+10+20-1 \times 6^2=24$ Mooney. Translated by ChatGPT 5