c++寻宝之路求解QWQ

Question

苦苦寻宝三十载，你发现了一座古墓。
这座墓是一个环状结构，共有 n 间室，第 i 与第 +1i+1 间室，第 n 与第 11 间室之间有可双向通行的小道。
入口联通第 1 间室，价值连城的宝藏在第 x 间室。通过一条小道需要 1分钟。拿起宝藏不需要时间。
你现在已经从入口走到了第 1 间室，想知道最快需要多少分钟才能拿起宝藏并回到第 1 间室。
输入格式
本题有多组测试数据。
第一行输入一个数
T，表示数据组数。
接下来 T 行，每行两个正整数代表 n 和 x，表示一组数据。
输出格式
对于每组数据输出一行一个正整数，代表至少需要多少分钟才能拿到宝藏并回到第 1 间室。
样例
Input 1
5
4 2
4 4
100000 50
100000 54321
1000000000 987654321
Output 1
2
2
98
91360
24691360

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

题目分析： 这是一道最短路问题。将墓所在的环形图看做无向图，可以使用 Dijkstra 算法或者 Floyd 算法求解。首先需要构建邻接矩阵，记录每两个室之间的距离。由于是环形图，需要特判第 n 间室到第 1 间室的距离。 Dijkstra 算法： 从第 1 间室开始，记录到每个室需要的最短时间。每次选择一条当前距离最短的边进行松弛操作，更新到每个室的最短时间。直到找到宝藏所在的室，此时的距离就是最短时间。 时间复杂度：O(n^2)，对于本题可通过。 Floyd 算法： 用邻接矩阵存储距离，二重循环加一个外层循环，依次将每个室看做中间点，更新其到其他每个室的距离，直到找到宝藏所在的室，此时的距离就是最短时间。 时间复杂度：O(n^3)，对于本题也可通过。 参考代码： Dijkstra 算法： 使用邻接表+堆优化可将时间复杂度降到 O(mlogn)，但因本题数据较弱，使用邻接矩阵即可，解题时务必仔细不要输错邻接矩阵。