2944 - Gangster´s Killer 2944 - Gangster´s Killer 2944 - Gangster´s Killer

Statistics Sub: 101 | AC: 49 | AC%: 48,51 | Score: 2,35
Created by Yonny Mondelo Hernández
Added by ymondelo20 (2014-06-09)
Limits
Total Time: 120000 MS | Test Time: 3000 MS |Memory: 62 MB | Output: 64 MB | Size: 14 KB
Enabled languages
Available in

Description

A big group of gangsters is whipping the eastern province of Leward; they kill children´s and rape women´s the whole time. So you have been hired for killing them for a huge amount of money. The only problem is that for each gangster you kill an important amount of money is released in a special account called MPC (Money Paid for Capture) which is equivalent to a prize for the killer who catch you. Yes, the MPC account is your head´s prize.

Each time you kill a gangster their friends who are still alive will pay for your capture. Each gangster will pay every time you kill one of their friends a fixed amount of money. They have a lot of money in their personal accounts so they always pays, looking for someone who kill you. You need to find one order for killing all the gangsters for which the total amount in the MPC account is the minimum possible.
;jsessionid=53ADC5230F1D11BCE27C9136C98EF529
A big group of gangsters is whipping the eastern province of Leward; they kill children´s and rape women´s the whole time. So you have been hired for killing them for a huge amount of money. The only problem is that for each gangster you kill an important amount of money is released in a special account called MPC (Money Paid for Capture) which is equivalent to a prize for the killer who catch you. Yes, the MPC account is your head´s prize.

Each time you kill a gangster their friends who are still alive will pay for your capture. Each gangster will pay every time you kill one of their friends a fixed amount of money. They have a lot of money in their personal accounts so they always pays, looking for someone who kill you. You need to find one order for killing all the gangsters for which the total amount in the MPC account is the minimum possible.
;jsessionid=53ADC5230F1D11BCE27C9136C98EF529
A big group of gangsters is whipping the eastern province of Leward; they kill children´s and rape women´s the whole time. So you have been hired for killing them for a huge amount of money. The only problem is that for each gangster you kill an important amount of money is released in a special account called MPC (Money Paid for Capture) which is equivalent to a prize for the killer who catch you. Yes, the MPC account is your head´s prize.

Each time you kill a gangster their friends who are still alive will pay for your capture. Each gangster will pay every time you kill one of their friends a fixed amount of money. They have a lot of money in their personal accounts so they always pays, looking for someone who kill you. You need to find one order for killing all the gangsters for which the total amount in the MPC account is the minimum possible.
;jsessionid=53ADC5230F1D11BCE27C9136C98EF529

Input specification

The first line contain a integer number 1 <= N <= 500 representing the amount of gangsters in Leward. Gangsters are conveniently numbered between 1 and N. The following N lines contain a integer number between 1 and 99; the amount of money that i-th gangster will pay for MPC account each time you kill one of their friends.

Then an arbitrary amount of pair of gangsters will be given, one pair per line. A single pair will be given as two distinct numbers A and B, both between 1 and N: this mean that gangsters A and B are friends. You can safely assume that no pair will be given twice in the input.
;jsessionid=53ADC5230F1D11BCE27C9136C98EF529
The first line contain a integer number 1 <= N <= 500 representing the amount of gangsters in Leward. Gangsters are conveniently numbered between 1 and N. The following N lines contain a integer number between 1 and 99; the amount of money that i-th gangster will pay for MPC account each time you kill one of their friends.

Then an arbitrary amount of pair of gangsters will be given, one pair per line. A single pair will be given as two distinct numbers A and B, both between 1 and N: this mean that gangsters A and B are friends. You can safely assume that no pair will be given twice in the input.
;jsessionid=53ADC5230F1D11BCE27C9136C98EF529
The first line contain a integer number 1 <= N <= 500 representing the amount of gangsters in Leward. Gangsters are conveniently numbered between 1 and N. The following N lines contain a integer number between 1 and 99; the amount of money that i-th gangster will pay for MPC account each time you kill one of their friends.

Then an arbitrary amount of pair of gangsters will be given, one pair per line. A single pair will be given as two distinct numbers A and B, both between 1 and N: this mean that gangsters A and B are friends. You can safely assume that no pair will be given twice in the input.
;jsessionid=53ADC5230F1D11BCE27C9136C98EF529

Output specification

A integer number: the minimum possible amount of money in the MPC account after killing all gangsters in Leward.
A integer number: the minimum possible amount of money in the MPC account after killing all gangsters in Leward.
The first line contain a integer number 1 <= N <= 500 representing the amount of gangsters in Leward. Gangsters are conveniently numbered between 1 and N. The following N lines contain a integer number between 1 and 99; the amount of money that i-th gangster will pay for MPC account each time you kill one of their friends.

Then an arbitrary amount of pair of gangsters will be given, one pair per line. A single pair will be given as two distinct numbers A and B, both between 1 and N: this mean that gangsters A and B are friends. You can safely assume that no pair will be given twice in the input.
;jsessionid=53ADC5230F1D11BCE27C9136C98EF529

Sample input

7
40
10
20
10
20
80
40
1 6
6 4
4 7
5 4
1 5
4 3
1 4
5 7
1 3
2 5

Sample output

160

Hint(s)




Recommendation

We have carefully selected several similar problems: 3675 | 3166 | 1005 | 3091 | 3303 | 2756