結果
問題 | No.2287 ++ -- *=a /=a |
ユーザー |
👑 |
提出日時 | 2024-04-29 22:21:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,532 ms / 2,000 ms |
コード長 | 1,288 bytes |
コンパイル時間 | 449 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 97,896 KB |
最終ジャッジ日時 | 2024-11-19 06:59:03 |
合計ジャッジ時間 | 15,524 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 |
ソースコード
from heapq import *def solve():x, y, a = map(int, input().split())E = []X = [x, y]s = xt = ywhile x > 0:nx = x // aX.append(nx)E.append((x, nx, 1))x = nxwhile y > 0:ny = y // aE.append((ny, ny * a, 1))E.append((ny + 1, (ny + 1) * a, 1))E.append((ny, ny + 1, 1))E.append((ny + 1, ny, 1))X.append(ny)X.append(ny * a)X.append(ny + 1)X.append((ny + 1) * a)y = nyX_ = sorted(list(set(X)))X = {x: i for i, x in enumerate(X_)}le = len(X)edges = [[] for _ in range(le)]for u, v, c in E:edges[X[u]].append((X[v], c))for i in range(le - 1):d = X_[i + 1] - X_[i]edges[i].append((i + 1, d))edges[i + 1].append((i, d))dist = [1 << 60] * les = X[s]t = X[t]dist[s] = 0hq = [s]while hq:tmp = heappop(hq)d = tmp // lepos = tmp - le * dif dist[pos] < d:continuefor npos, c in edges[pos]:nd = d + cif nd < dist[npos]:dist[npos] = ndheappush(hq, nd * le + npos)print(dist[t])for _ in range(int(input())):solve()