2013年7月18日 星期四

10662 - The Wedding

  The Wedding  

Background

Felix 和 Leti 即將要結婚了,每個人正準備給他們這對新人禮物,但是他們的預算並不多,他們想要讓他們有一個不錯的餐廳,以及在一個高級旅館睡了一晚,接著再環遊世界的蜜月旅行。

希望能得到最便宜的價格包含上述的行程內容,湊出旅行、餐廳、旅館的行程。

The Problem


我們必須找到最便宜的 旅行社-餐廳-旅館 的組合,但並不是每種組合都可以。

The Input

每組測資的格式如下:
  • 第一行有三個整數 T, R, H,分別表示旅行社、餐廳、旅館的數量。
    T < 20, R < 20 , H < 20.  且三者的編號皆從 0, 1, 2, ...
  • 接下來會有  T+R+H  行,分別有三個區塊:
    • T 行,每行上有 R+1 個整數,第一個整數表示該旅行社的花費,而接下來 R 個整數表示 cell(i,j),表示旅行社(i)是否可以跟餐廳(j)搭配,cell(i,j) = 0 表示可以,反之不行。
    • 接下來 R 行,每行上有 H+1 個整數,第一個整數表示該餐廳的花費,而接下來 H 個整數表示 cell(i,j),表示餐廳(i)是否可以跟旅館(j)搭配,cell(i,j) = 0 表示可以,反之不行。
    • 接下來 H 行,每行上有 T+1 個整數,第一個整數表示該旅館的花費,而接下來 T 個整數表示 cell(i,j),表示旅館(i)是否可以跟旅行社(j)搭配,cell(i,j) = 0 表示可以,反之不行。

The Output

對於每組輸出格式如下:

T R H:P

分別表示旅行社編號、餐廳編號、旅館編號以及最便宜的花費。

如果不存在任何組合,則輸出:Don't get married!

如果有多組可能,任何一組都可以。

Sample Input

2 2 2
12 0 0
1 1 1
34 0 0
3 1 1
21 1 0
2 1 0
2 2 2
12 0 0
1 0 0
34 0 0
3 0 0
21 0 0
2 0 0
5 5 6
970 0 1 1 1 0 
856 0 0 0 0 0 
1290 1 0 0 1 0 
1361 0 0 1 0 0 
82 0 0 0 0 1 
1182 0 0 0 1 1 0 
450 0 1 1 0 0 1 
895 0 0 1 0 1 1 
1865 0 1 0 0 1 1 
183 1 1 1 1 1 0 
252 1 1 1 0 1 
1813 1 0 0 1 1 
1429 0 0 1 0 0 
1522 1 1 1 0 0 
1762 0 0 1 0 1 
1946 0 1 0 0 0 

Sample Output

Don't get married!
1 1 1:6
4 1 3:2054