## GENESIS

View as PDF

Points: 20
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 ships labeled , with GENESIS labeled . Destroying the ship requires energy. Athrun also knows that there are connections of the form between ships. Each connection means that ship can pass a one-way signal to ship . Athrun would like to destroy a number of ships so that ship cannot send a signal to ship . Of course, the GENESIS may not 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 has the integer . The next lines contain the values .

Line contains the integer . The next lines contains two integers, and denoting a connection between ship and ship .

#### Output Specification

An integer denoting the minimum energy required to cut connections between ship and .

3
4
3
2
1 2
2 3

#### Sample Output

3

• commented on June 29, 2019, 9:56 a.m. edit 4

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on June 30, 2019, 7:07 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on July 27, 2017, 5:12 p.m. edited

MLE

Any hints as to why I'm MLEing?

Nvm, I recursed too early

• commented on July 27, 2017, 6:16 p.m.

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

• commented on July 27, 2017, 7:01 p.m.

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

• commented on July 27, 2017, 7:17 p.m.

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

• commented on April 11, 2016, 9:34 p.m.

Is my approach to this problem wrong?

Is O(V) algorithm too slow?

• commented on Oct. 3, 2015, 10:36 p.m.

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