MOBIVINA - MobiZone vs VinaGone

Trong đợt thử nghiệm công nghệ mới của MobiZone và VinaGone, CEO của hai tập đoàn viễn thông này là KTuấn và AnhDQ đã kí một hợp đồng liên kết giúp hai nhà cung cấp dịch vụ viễn thông này có thể sử dụng chung mạng lưới của nhau. Có N người tiến hành tham gia đợt thử nghiệm này. Biết rằng người thứ i cần trả một khoản chi phí là Mi nếu sử dụng dịch vụ của MobiZone, hoặc Vi nếu sử dụng dịch vụ của VinaGone; đồng thời hai người thứ i và j bất kì chấp nhận trả chung một khoản chi phí là Cij nếu sử dụng dịch vụ của hai nhà cung cấp khác nhau (để trả phí cho dịch vụ liên kết).

Yêu cầu

Hãy tư vấn cho N người này lựa chọn một trong hai dịch vụ mạng sao cho tổng chi phí mà N người phải bỏ ra là nhỏ nhất. Cho biết chi phí nhỏ nhất đó.

Dữ liệu

- Dòng đầu tiên chứa số N.
- Dòng thứ hai chứa N số Mi.
- Dòng thứ ba chứa N số Vi.
- N dòng cuối cùng, mỗi dòng N số Cij (Cij = Cji).

Kết quả

- Gồm một số duy nhất là chi phí nhỏ nhất tìm được.

Ví dụ

Dữ liệu:
3
1 1 10
10 10 1
0 0 1
0 0 1
1 1 0

Kết quả:
5

Giới hạn

- N ≤ 250.
- Các số còn lại trong Input không vượt quá 1000.


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)

hide comments
2021-01-12 04:36:49
Another similar problem: LightOJ 1361 - Component Placement
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
2013-02-26 15:28:06 Alex Abbas
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...
2012-08-30 16:56:31 Ajey Golsangi
The problem statement is unclear. Please rectify the grammar in the problem statement.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.