The Cosmic Era P5 - GENESIS

View as PDF

Submit solution

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

Author:
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 (2 \le N \le 100) ships labeled 1 \dots N, with GENESIS labeled N. Destroying the i^\text{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 \to 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 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. 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 contain 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


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

    Is my approach to this problem wrong?

    Is O(VE^2) algorithm too slow?


  • 11
    bruce  commented on Oct. 4, 2015, 2:36 a.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.