← 返回题目列表

AtCoder · tenka1_2012_11

C. 更换座位

中文机器翻译题面 查看原题

問題文

迅速成长中的K公司,由于高节奏的采用,座位已经不够了。
下一处办公室的搬迁地点已经决定了,但由于一些成人的原因,决定扩大现有办公室。
由于办公室变大了,所以需要更换。
K公司非常忙碌,所以不想在换座位上花费太多时间。


您必须使用手推车更换座位。
将行李放在推车上的座位上 花了 5 分钟才把行李从车上卸下到座位上。 需要 5 分钟。
1 购物车有 1 只能携带一个人的行李。
此时,从您开始装载推车到您卸完为止,均视为推车装载有行李,您不能在上面放置其他人的行李。
如果您要前往的座位上有行李,您将无法卸下它。
此时,假设座位上有行李,直到座位上的行李已经装到推车上。
此外,即使您没有换座位,也可以暂时将行李卸下到没有行李的座位上,但不能将多人的行李放在一个座位上。

根据换座前后的座位表以及推车数量,计算换座所需的最短时间。
推车的性能非常好,装完行李后应该不会花很长时间就可以移动到目的地座位。


入力

输入是按以下格式从标准输入给出的。
N M L
a_{1} b_{1}
:
a_{L} b_{L}
  • 输入是 L+1 。
  • 第一行表示座位数。 N ( 1 \leq N \leq 30 )和 代表购物车的数量 M ( 1 \leq M \leq N )和 代表员工人数 L ( 1 \leq L \leq N 和 L \leq 15 ) 用空格分隔。 在
  • 从第二行开始 L 行包含 i ( 1 \leq i \leq L ) 换座前的第号员工座位号 a_{i} ( 1 \leq a_{i} \leq N ) 以及换座后的座位号 b_{i} ( 1 \leq b_{i} \leq N ) 用空格分隔。 在
  • i \neq j 如果 a_i \neq a_j 。
  • i \neq j 如果 b_i \neq b_j 。

部分点

输入少量席位( 如果只有 1 \leq N \leq 7 ) 是正确的,那么100 部分积分换满分 50 点。 如果您正确回答了所有满足

出力

打印更换座位所需的最短时间(以分钟为单位)。
如果无法更换座位, -1 。
请注意,行尾需要换行。 定义

入力例 1

3 3 3
1 2
2 3
3 1

出力例 1

10
  • 开始换座位时,开始将三人的行李装载到三辆推车上。
  • 开始换座位五分钟后,我们开始把三个人的行李卸到各自的目的地。
  • 通过以上步骤,10分钟内即可完成换座。

入力例 2

3 2 3
1 2
2 3
3 1

出力例 2

20
  • 更换座位的示例如下所示。
  • 当您开始更换座位时,开始将 1 号和 2 号座位的行李装载到购物车上。
  • 换座开始五分钟后,1号座位上的行李开始从车上卸载到2号座位。
  • 换座开始10分钟后,3号座位的行李开始装上车。
  • 换座开始15分钟后,两人开始将行李卸到推车上前往各自的目的地。
  • 通过以上步骤,20分钟内即可完成换座。

入力例 3

3 1 3
1 2
2 3
3 1

出力例 3

-1
  • 在这种情况下,无法更换座位。

入力例 4

4 1 3
1 2
2 3
3 1

出力例 4

40
  • 在这种情况下,您可以在 40 分钟内使用空座位更换座位。