Time is Mooney

题目描述

Bessie 正在 Bovinia 出差，这里有 $N$（$2\le N\le 1000$）个城市，标号为 $1\ldots N$，它们由 $M$（$1\le M\le 2000$）条单向道路连接。每次 Bessie 访问城市 $i$ 时，她会赚到 $m_i$ 个 moonies（$0\le m_i\le 1000$）。Bessie 从城市 1 出发，希望通过访问一些城市来赚取尽可能多的 mooney，最后回到城市 1。为避免混淆，规定 $m_1=0$。

通过一条道路在两个城市之间移动需要一天。为这次旅行做准备很昂贵：旅行 $T$ 天的花费为 $C\cdot T^2$ 个 moonies（$1\le C\le 1000$）。

求 Bessie 在一次旅行中最多能赚到多少 moonies？注意，最优策略可能是不访问除城市 1 以外的任何城市，此时答案为 0。

输入格式

第一行包含三个整数 $N$、$M$ 和 $C$。 第二行包含 $N$ 个整数 $m_1,m_2,\ldots m_N$。 接下来 $M$ 行每行包含两个用空格分隔的整数 $a$ 和 $b$（$a\neq b$），表示一条从城市 $a$ 到城市 $b$ 的单向道路。

输出格式

输出一行，包含答案。

3 3 1
0 10 20
1 2
2 3
3 1

24

提示

最优的旅行是 $1\to 2\to 3 \to 1\to 2\to 3\to 1.$ Bessie 总共获得 $10+20+10+20-1\cdot 6^2=24$ 个 moonies。 题目作者：Richard Peng 和 Mark Gordon

标签: USACO|2020|Gold

来源

USACO|2020|Gold