The Cosmic Era P5 - GENESIS - Olympiads Online Judge

The Cosmic Era P5 - GENESIS

View as PDF

Submit solution

All submissions

Best submissions

Points: 20

Time limit: 1.0s

Memory limit: 64M

Author:

LOLWHATOMGBBQ

Problem type

ZAFT is about to fire its superweapon GENESIS and destroy the Earth! It's up to Athrun to stop them from activating the GENESIS. In order to activate the GENESIS, a ship must send a signal to GENESIS telling it to activate, but sometimes the ship's range isn't far enough and cannot reach the GENESIS. To reach GENESIS, a ship will send a signal to neighbouring ships, telling them to send a signal to other neighbouring ships, eventually reaching the GENESIS. Athrun knows that there are $N$ ~N~ $(2 \le N \le 100)$ ~(2 \le N \le 100)~ ships labeled $1 \dots N$ ~1 \dots N~, with GENESIS labeled $N$ ~N~. Destroying the $i^\text{th}$ ~i^\text{th}~ ship requires $E_i$ ~E_i~ $(1 \le E_i \le 1\,000)$ ~(1 \le E_i \le 1\,000)~ energy. Athrun also knows that there are $M$ ~M~ $(N \le M \le 1\,000)$ ~(N \le M \le 1\,000)~ connections of the form $i \to j$ ~i \to j~ between ships. Each connection means that ship $i$ ~i~ can pass a one-way signal to ship $j$ ~j~. Athrun would like to destroy a number of ships so that ship $1$ ~1~ cannot send a signal to ship $N$ ~N~. Of course, the GENESIS cannot be destroyed.

He would like to spend the least amount of energy in disconnecting the ships, and has asked you to help him find this amount.

Input Specification

First line contains the integer $N$ ~N~. The next $N-1$ ~N-1~ lines contain the values $E_1 \dots E_{N-1}$ ~E_1 \dots E_{N-1}~.

Line $N+1$ ~N+1~ contains the integer $M$ ~M~. The next $M$ ~M~ lines contain two integers, $i$ ~i~ and $j$ ~j~ denoting a connection between ship $i$ ~i~ and ship $j$ ~j~.

Output Specification

An integer denoting the minimum energy required to cut connections between ship $1$ ~1~ and $N$ ~N~.

Sample Input

Sample Output

Comments

1

eric574 commented on July 27, 2017, 9:12 p.m. ← edited →

MLE

Any hints as to why I'm MLEing?

Nvm, I recursed too early

1

wleung_bvg commented on July 27, 2017, 10:16 p.m.

It looks like you have an infinite loop (seems to be the DFS function).

1

eric574 commented on July 27, 2017, 11:01 p.m.

Thx for the suggestion, but I thought that that was part of the algorithm.

2

wleung_bvg commented on July 27, 2017, 11:17 p.m.

I was suggesting that your dfs function was never finishing, but perhaps I was wrong (I probably was).

6

XIAOAGE commented on April 12, 2016, 1:34 a.m. ← edited →

Is my approach to this problem wrong?

Is $\mathcal{O}(VE^2)$ ~\mathcal{O}(VE^2)~ algorithm too slow?

12

bruce commented on Oct. 4, 2015, 2:36 a.m.

If ship 1 cannot be destroyed, what's the meaning of $E_1$ ~E_1~? Is it the energy required to destroy ship 1? If I just ignore $E_1$ ~E_1~, my solution got WA. But if I consider $E_1$ ~E_1~, it is correct.