- 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
- #include <iostream>
- using namespace std;
- int Map[21][21] = { 0 }; // 邻接矩阵
- int path[21]; // 记录每一次答案的路线
- bool visited[21] = { false };
- int num = 1; // 路径的编号
- void dfs(int city, int cur) //city 为当前访问的城市, 已经访问了 cur 个城市
- {
- path[cur] = city; // 将当前城市记录在路径上
- visited[city] = true;
- if (cur == 20) // 如果已经访问了 20 个城市
- {
- if (Map[city][path[1]] == 1) // 这个城市与起点城市之间存在路径
- {
- cout <<num << ":";
- num++;
- for (int i = 1; i <= 20; ++i)
- cout << path[i] << ' ';
- cout << path[1] << endl;
- }
- }
- for (int i = 1; i <= 20; ++i)
- {
- if (Map[i][city] == 1 && !visited[i])
- {
- dfs(i, cur+1); // 注意此处不能是 ++cur
- visited[i] = false; //dfs 完要把访问过的顶点重新置为未访问状态
- }
- }
- }
- int main()
- {
- // 创建邻接矩阵
- int city;
- for (int i = 1; i <= 20; ++i)
- {
- for (int j = 1; j <= 3; ++j)
- {
- cin>> city;
- Map[i][city] = 1;
- }
- }
- int m;
- while (cin>> m && m != 0)
- {
- dfs(m, 1);
- num = 1;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945375.html