← 返回题目列表

AtCoder · abc183_c

C. 旅行

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

分数: 300 点

问题陈述

有 N 城市。从 City 出发所需时间 i 前往城市 j is T_{i, j}.

在从 City 开始的路径中 1,访问所有其他城市一次,然后返回 City 1,有多少条路径总共花费了 K 一起旅行?

约束

  • 2\leq N \leq 8
  • If i\neq j, 1\leq T_{i,j} \leq 10^8.
  • T_{i,i}=0
  • T_{i,j}=T_{j,i}
  • 1\leq K \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
T_{1,1} \ldots T_{1,N}
\vdots
T_{N,1} \ldots T_{N,N}

输出

将答案打印为整数。


示例输入 1

4 330
0 1 10 100
1 0 20 200
10 20 0 300
100 200 300 0

示例输出 1

2

有 6 条路径从 City 开始 1,访问所有其他城市一次,然后返回 City 1:

  • 1\to 2\to 3\to 4\to 1
  • 1\to 2\to 4\to 3\to 1
  • 1\to 3\to 2\to 4\to 1
  • 1\to 3\to 4\to 2\to 1
  • 1\to 4\to 2\to 3\to 1
  • 1\to 4\to 3\to 2\to 1

沿着这些路径行驶所需的时间是 421, 511, 330, 511, 330,和 421,其中两个正好是 330.


示例输入 2

5 5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

示例输出 2

24

无论我们以什么顺序访问这些城市,总时间将是 5 去旅行。