翻译
查看原帖
翻译
161223
东方澂楼主2022/1/16 15:26

题目描述
Felix和Leti马上就要结婚了,但是他们面临着一个难题:钱。他们的预算并不高。他们想要找一家好的餐厅,在一家好的酒店度过初夜并且环球旅行度蜜月。这有可能吗?我们需要找到最便宜的旅行社、餐厅、酒店的组合。问题是并未所有组合都是可以的。

输入格式
每组测试数据的格式如下:

第一行包含三个整数T, R, H(T, R, H ≤ 20),分别表示旅行社、餐厅和酒店的数量。旅行社、餐厅和酒店编号为0, 1, 2……

接下来的T + R + H行可以分为三部分:
第一部分有T行R + 1列。第一列是旅行社提供的环球旅行的价格。在剩余的“表格”中,如果旅行社i可以和餐厅j组合,单元格(i, j)为0,不能则为1。
第二部分有R行H + 1列。第一列是餐厅的价格。在剩余的“表格”中,如果餐厅i可以和酒店j组合,单元格(i, j)为0,不能则为1。
第三部分有H行T + 1列。第一列是酒店的价格。在剩余的“表格”中,如果酒店i可以和旅行社j组合,单元格(i, j)为0,不能则为1。

输入以一行空行结束。

输出格式
对于每组数据,如果无解,则输出Don't get married!;如果有解,输出旅行社、餐厅、酒店的编号T, R, H以及最低总价格P,格式为T R H:P;如果有多解,输出任意一个。

2022/1/16 15:26
加载中...