24 hour archive: Problem
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 (20140609) 
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
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.
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
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.
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
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.
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 ith 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
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.
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 ith 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
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.
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 ith 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
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.
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 ith 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
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.
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