2024-01-01 18:45 四川民族学院 测试工程师
关注
基站维修工程师
#牛客在线求职答疑中心#基站维修工程师
题目描述
小王是一名基站维护工程师，负责某区域的基站维护。某地方有n个基站（1 < n < 10），已知各基站之间的距离s（0 < s < 500），并且基站x到基站y的距离，与基站y到基站x的距离并不一定会相同。
小王从基站1出发，途径每个基站1次，然后返回基站1，需要请你为他选择一条距离最短的路径。
输入描述
第一行表示站点数，以后各行表示站点数n到各站点之间的距离（均为整数）。
3
0 2 1
1 0 2
2 1 0
Copy to clipboardErrorCopied
输出描述
最短路径的数值。
示例描述
示例一
输入：
3
0 2 1
1 0 2
2 1 0
Copy to clipboardErrorCopied
输出：
3
Copy to clipboardErrorCopied
解题思路
本题采用可放回的回溯法。
由于固定从基站1开始，可设置初始路径列表为[0]，路径长度和路径节点一致，使用回溯法得到所有可能的路径。
根据得到的路径，计算路径长度，得到最小路径。
题目描述
小王是一名基站维护工程师，负责某区域的基站维护。某地方有n个基站（1 < n < 10），已知各基站之间的距离s（0 < s < 500），并且基站x到基站y的距离，与基站y到基站x的距离并不一定会相同。
小王从基站1出发，途径每个基站1次，然后返回基站1，需要请你为他选择一条距离最短的路径。
输入描述
第一行表示站点数，以后各行表示站点数n到各站点之间的距离（均为整数）。
3
0 2 1
1 0 2
2 1 0
Copy to clipboardErrorCopied
输出描述
最短路径的数值。
示例描述
示例一
输入：
3
0 2 1
1 0 2
2 1 0
Copy to clipboardErrorCopied
输出：
3
Copy to clipboardErrorCopied
解题思路
本题采用可放回的回溯法。
由于固定从基站1开始，可设置初始路径列表为[0]，路径长度和路径节点一致，使用回溯法得到所有可能的路径。
根据得到的路径，计算路径长度，得到最小路径。
全部评论
相关推荐
投递美团等公司10个岗位 点赞 评论 收藏
分享
10-21 19:49
门头沟学院 自动化测试 
点赞 评论 收藏
分享