Submit solution

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 N (2 \le N \le 100) ships labeled 1 \dots N, with GENESIS labeled N. Destroying the i^{th} ship requires E_i (1 \le E_i \le 1\,000) energy. Athrun also knows that there are M (N \le M \le 1\,000) connections of the form i \rightarrow j between ships. Each connection means that ship i can pass a one-way signal to ship j. Athrun would like to destroy a number of ships so that ship 1 cannot send a signal to ship N. 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 N. The next N - 1 lines contain the values E_1 \dots E_{N - 1}.

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

Output Specification

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

Sample Input

3
4
3
2
1 2
2 3

Sample Output

3

Comments


  • -6
    subscriber  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.


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

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


  • 2
    eric574  commented on July 27, 2017, 5: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, 6:16 p.m.

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


      • 2
        eric574  commented on July 27, 2017, 7: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, 7:17 p.m.

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


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

    Is my approach to this problem wrong?

    Is O(VE^2) algorithm too slow?


  • 8
    bruce  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.