MOBIVINA - MobiZone vs VinaGone
English | Tiếng Việt |
KTuan and AnhDQ, CEOs of two telecommunication corporations MobiZone and VinaGone have signed a contract to use their network in common. N people have accepted to try this new service. The ith people accepts to pay Mi to use MobiZone's service or Vi to use VinaGone's one; and any two people ith and jth accept to pay Cij in common whether they use different services (the network cost).
Request
Find a way of choosing networks for N people satisfying the sum of total cost is minimum.
Input
- The first line contains number N.
- The second line contains N number(s) Mi.
- The third line contains N number(s) Vi.
- The last N line(s), each of them contains N number(s) Cij (Cij = Cji).
Output
- Contains the minimum total cost.
Example
Input:
3
1 1 10
10 10 1
0 0 1
0 0 1
1 1 0
Output:
5
Limitations
- N ≤ 250.
- The remaining numbers of Input do not exceed 1000.
hide comments
treenipples:
2021-01-12 04:36:49
Another similar problem: LightOJ 1361 - Component Placement |
|
kesh4281:
2020-04-02 12:11:29
The last line of the statement means if two guys i and j use different services then they pay Cij (=Cji) once. |
|
যোবায়ের:
2013-03-27 15:32:11
@Alex Abbas, I think the possible explanation is, you assign person1 with Mobi, person2 with Mobi and person3 with Vina. Then they need to pay 1 + 1 + 1 individually. Also, person1 and person3 are using different network, so they pay C[1][3] more, same as person2 and person3, C[2][3] more. totalling 3 + 1 + 1 = 5 Last edit: 2013-09-19 05:40:15 |
|
Alex Abbas:
2013-02-26 15:28:06
I don't understand whether we need to connect all services to all people or just one service can u explain the input/output sample please... |
|
Ajey Golsangi:
2012-08-30 16:56:31
The problem statement is unclear. Please rectify the grammar in the problem statement. |
Added by: | AnhDQ |
Date: | 2009-06-08 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Mr Tuan Khuc Anh - NTU (Singapore) |