让阿豪来帮你解答,本回答参考chatgpt3.5编写提供,如果还有疑问可以评论或留言
题目描述
苦苦寻宝三十载,你发现了一座古墓。
这座墓是一个环状结构,共有n间室,第ii与第i+1i+1间室,第nn与第11间室之间有可双向通行的小道。
入口联通第11间室,价值连城的宝藏在第xx间室。
通过一条小道需要11分钟。拿起宝藏不需要时间。
你现在已经从入口走到了第11间室,想知道最快需要多少分钟才能拿起宝藏并回到第11间室。
输入格式
本题有多组测试数据。
第一行输入一个数T,表示数据组数。
接下来T 行,每行两个正整数代表n和x,表示一组数据。
输出格式
对于每组数据输出一行一个正整数,代表至少需要多少分钟才能拿到宝藏并回到第11间室。
样例
输入样例1:
5
4 2
4 4
100000 50
100000 54321
1000000000 987654321
输出样例1:
2
2
98
91360
24691360
算法
(BFS) $O(n)$
tip:最短路问题,可以尝试使用广度优先搜索算法BFS,用queue辅助, python语言优先考虑deque
python3 代码
C++ 代码
python
BFS做法,用的是list中pop(0)的方法,速度比较慢,但思路通俗易懂。
from collections import deque
x = deque()
while True:
try:
n, m = map(int, input().split())
except Exception:
break
x.append((n, m))
xxx = x while len(x) != 0: n, m = x.pop(0) visited = [False for i in range(n + 1)] distance = [1e9 for i in range(n + 1)] distance[1] = 0 visited[1] = True XX = [] for xx in range(1, n + 1): if xx == 1: continue if xx == n and 1 not in XX: XX.append(1) continue XX.append(xx - 1) XX.append(xx + 1) while len(XX) != 0: x_ = XX.pop(0) if x_ <= 0 or x_ > n or visited[x_]: continue visited[x_] = True distance[x_] = distance[x] + 1 if x_ == m: x.append(distance[m]) break XX.append(x_) for i in xxx: print(x.popleft()) C++ BFS C++ 代码 tip:不能用queue,在数据量较大时会超时,所以这利用数组进行队列操作,很快。 #include using namespace std; const int N = 1000005; int n, m, h, t; int q[N]; bool st[N]; int dist[N]; int path[N]; int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); // 对数组进行清零 memset(dist, 0, sizeof dist); memset(path, 0, sizeof path); memset(st, 0, sizeof st); h = 0, t = -1; q[++t] = 1; while (h <= t) { int x = q[h++]; for (int i = -1; i <= 1; i += 2) { int y = x + i; if (y > n) y = 1; if (y < 1) y = n; if (st[y] == false) { st[y] = true; if (dist[y] == 0 or dist[x] + 1 < dist[y]) { dist[y] = dist[x] + 1; path[y] = x;//y从x过来的 q[++t] = y;//让y入队 } } } } int ans = dist[m]; printf("%d\n", ans); } return 0; }