#PU993. USACO 2020 January Contest, Gold — Problem 1. Time is Mooney
USACO 2020 January Contest, Gold — Problem 1. Time is Mooney
USACO 2020 January Contest, Gold — Problem 1. Time is Mooney
题目描述
Bessie is conducting a business trip in Bovinia, where there are () cities labeled connected by () one-way roads. Every time Bessie visits city Bessie earns moonies (). Starting at city 1 Bessie wants to visit cities to make as much mooney as she can, ending back at city 1. To avoid confusion, Mooving between two cities via a road takes one day. Preparing for the trip is expensive; it costs moonies to travel for days (). What is the maximum amount of moonies Bessie can make in one trip? Note that it may be optimal for Bessie to visit no cities aside from city 1, in which case the answer would be zero.
输入格式
The first line contains three integers , , and . The second line contains the integers . The next lines each contain two space-separated integers and () denoting a one-way road from city to city .
输出格式
A single line with the answer.
数据范围
(见题面原文)
样例
样例 1
3 3 1
0 10 20
1 2
2 3
3 1
24
The optimal trip is $1\to 2\to 3 \to 1\to 2\to 3\to 1.$ Bessie makes
$10+20+10+20-1\cdot 6^2=24$ moonies in total.
Problem credits: Richard Peng and Mark Gordon