Sample Input

2 5 20

1 3 12

2 4 10

3 5 8

1 4 6

5 7 19

6 8 17

4 7 9

8 10 16

3 9 11

10 12 15

2 11 13

12 14 20

13 15 18

11 14 16

9 15 17

7 16 18

14 17 19

6 18 20

1 13 19

5

0

 

Sample Output

 

1 #include 
       
         2  3 using namespace std; 4  5 int Map[21][21] = { 0 };  //邻接矩阵 6 int path[21];              //记录每一次答案的路线 7 bool visited[21] = { false }; 8 int num = 1; //路径的编号 9 10 11 void dfs(int city, int cur) //city为当前访问的城市，已经访问了cur个城市12 {13     path[cur] = city;    //将当前城市记录在路径上14     visited[city] = true;15 16     if (cur == 20)        //如果已经访问了20个城市17     {18         if (Map[city][path[1]] == 1)    //这个城市与起点城市之间存在路径19         {20             cout << num << ":  ";21             num++;22             for (int i = 1; i <= 20; ++i)    23                 cout << path[i] << ' ';24             cout << path[1] << endl;25         }26     }27 28     for (int i = 1; i <= 20; ++i)29     {30         if (Map[i][city] == 1 && !visited[i])31         {32             dfs(i, cur+1);        //注意此处不能是++cur33             visited[i] = false;    //dfs完要把访问过的顶点重新置为未访问状态34         }35     }36 37 }38 39 40 int main()41 {42     //创建邻接矩阵43     int city;44     for (int i = 1; i <= 20; ++i)45     {46         for (int j = 1; j <= 3; ++j)47         {48             cin >> city;49             Map[i][city] = 1;50         }51     }52 53     int m;54     while (cin >> m && m != 0)55     {56         dfs(m, 1);57         num = 1;58     }59 60 61     return 0;62     63 }