题目分析

这道题要求找到一种方式，以最少的公交乘坐次数游览完所有景点。我们可以把这道题理解成一个访问所有点至少一次的最短路径问题。类似于经典的旅行商问题（TSP），但稍有不同的是——每个景点允许重复访问。

思路：Floyd 最短路 + 状压 DP

为了解决这个问题，我们将使用 Floyd-Warshall 算法结合状态压缩动态规划（DP），来找到访问所有景点的最短路径（即乘坐公交的最少次数）。其中，Floyd-Warshall 用于预处理两点之间的最短路径，状态压缩 DP 则用于计算如何最少次数地遍历所有景点。

思路详解

题目内容

春节将近，小明想在节日期间逛一逛城里的 $N$ 个著名景点，正好所有的景点都能通过坐公交到达，请帮小明设计一下，怎么搭乘公交路线才能最快逛完所有的景点。

1、景点编号 $0,1,2,…,N-1$

2、用数组 $arr[N] [N]$表示景点和景点之间是否有直达公交路线相连

3、$arr[i] [j]=1$ 表示景点 $i$ 和景点 $j$ 之间有直达公交相连，$arr[i] [j] =0$ 表示没有

4、公交可以双向行驶，即如果 $arr[i] [j]=1$，则必然 $arr[i] [j]=1$

5、每个景点可以经过多次，两个景点的公交也可以坐多次

6、可以从任一景点开始游玩

输入描述

第一行:景点数量 $N(0<N<=20)$

后续 $N$ 行: $N$ 个元素表示景点与景点之间的公交到达关系

输出描述

最少乘坐公交的次数(如果不能逛完所有景点，则输出 $0$ )

样例1

输入

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

输出

4

说明

样例2

输入

6
0 1 1 0 0 0
1 0 0 0 0 0
1 0 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0

输出

6

说明