레이팅 미적용베시는 보비니아(Bovinia)로 출장을 왔다. 이곳에는 \(1\ldots N\)로 번호가 붙은 \(N\)개(\(2\le N\le 1000\))의 도시가 \(M\)개(\(1\le M\le 2000\))의 일방통행 도로로 연결되어 있다. 베시가 도시 \(i\)를 방문할 때마다 베시는 \(m_i\)무니(\(0\le m_i\le 1000\))를 번다. 도시 1에서 출발한 베시는 여러 도시를 방문하며 가능한 한 많은 무니를 벌고, 다시 도시 1로 돌아와 여행을 마치고 싶다. 혼동을 피하기 위해 \(m_1=0\)이다.
도로를 통해 두 도시 사이를 이동하는 데는 하루가 걸린다. 여행 준비에는 비용이 많이 든다. \(T\)일 동안 여행하려면 \(C\cdot T^2\)무니가 든다(\(1\le C\le 1000\)).
베시가 한 번의 여행에서 벌 수 있는 무니의 최대 액수는 얼마인가? 도시 1 외에는 아무 도시도 방문하지 않는 것이 최적일 수도 있으며, 이 경우 답은 0이 됨에 유의하라.
문제 제공: Richard Peng and Mark Gordon
문제 제공: Richard Peng and Mark Gordon
첫째 줄에 세 정수 \(N\), \(M\), \(C\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(m_1,m_2,\ldots m_N\)이 주어진다.
다음 \(M\)개의 줄에는 각각 공백으로 구분된 두 정수 \(a\)와 \(b\)(\(a\neq b\))가 주어지며, 이는 도시 \(a\)에서 도시 \(b\)로 가는 일방통행 도로를 나타낸다.
답을 한 줄에 출력한다.
time.in · 출력을 쓸 파일 time.out3 3 1
0 10 20
1 2
2 3
3 124The 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.