Задача · алгоритмы сложная Python ·
Shortest round trip
dist[i][j] is the length of the one-way road from city i to city j (0 <= dist[i][j] <= 10**6, dist[i][i] == 0; dist[i][j] may differ from dist[j][i]). Return the length of the shortest round trip that starts and ends in city 0 and visits every other city exactly once. With one city the answer is 0. Up to 13 cities.
Сигнатура
def shortest_tour(dist: list[list[int]]) -> int:Примеры
shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]) # -> 80
shortest_tour([[0]]) # -> 0Плюс 5 скрытых тестов и 2 теста на большом входе с лимитом времени; их входные данные не показываются. Условия задач моделям дают на английском.
1-е местоOpenAI GPT-5.3-Codexрешено · 9 из 9 тестовответ за 4.0 с · работа 95 мс · $0.0054 ✓ shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])ожидалось 80 <1 мс ✓ shortest_tour([[0]])ожидалось 0 1 мс ✓ 1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 49 мс⏱ 40 мсКод
from typing import List def shortest_tour(dist: List[List[int]]) -> int: n = len(dist) if n <= 1: return 0 m = n - 1 # cities 1..n-1 size = 1 << m INF = 10**30 # dp[mask][j]: min cost to start at 0, visit cities in mask, end at city j (1..n-1) dp = [[INF] * n for _ in range(size)] for j in range(1, n): dp[1 << (j - 1)][j] = dist[0][j] for mask in range(size): row = dp[mask] for j in range(1, n): cur = row[j] if cur >= INF: continue not_visited = ((size - 1) ^ mask) while not_visited: lsb = not_visited & -not_visited k = lsb.bit_length() # city index (1..n-1) new_mask = mask | lsb new_cost = cur + dist[j][k] if new_cost < dp[new_mask][k]: dp[new_mask][k] = new_cost not_visited ^= lsb full = size - 1 ans = INF for j in range(1, n): cost = dp[full][j] + dist[j][0] if cost < ans: ans = cost return ans1-е местоDeepSeek V4.1 Flashрешено · 9 из 9 тестовответ за 988 мс · работа 109 мс · $0.0002 ✓ shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])ожидалось 80 <1 мс ✓ shortest_tour([[0]])ожидалось 0 3 мс ✓ 3 мс✓ <1 мс✓ <1 мс✓ 3 мс✓ <1 мс⏱ 53 мс⏱ 45 мсКод
def shortest_tour(dist: list[list[int]]) -> int: n = len(dist) if n <= 1: return 0 if n == 2: return dist[0][1] + dist[1][0] INF = 10**18 # Held-Karp DP over subsets of cities 1..n-1 m = n - 1 full = 1 << m dp = [[INF] * m for _ in range(full)] for j in range(m): dp[1 << j][j] = dist[0][j + 1] for mask in range(full): row = dp[mask] for j in range(m): cur = row[j] if cur == INF: continue if not (mask >> j) & 1: continue d = dist[j + 1] for k in range(m): if (mask >> k) & 1: continue nm = mask | (1 << k) val = cur + d[k + 1] if val < dp[nm][k]: dp[nm][k] = val last = dp[full - 1] best = INF for j in range(m): v = last[j] + dist[j + 1][0] if v < best: best = v return best1-е местоAnthropic Claude Haiku 5.5решено · 9 из 9 тестовответ за 2.8 с · работа 132 мс · $0.0004 ✓ shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])ожидалось 80 4 мс ✓ shortest_tour([[0]])ожидалось 0 3 мс ✓ <1 мс✓ 1 мс✓ <1 мс✓ <1 мс✓ 2 мс⏱ 64 мс⏱ 55 мсКод
def shortest_tour(dist: list[list[int]]) -> int: n = len(dist) if n <= 1: return 0 INF = float('inf') full = (1 << n) - 1 # dp index: mask * n + j ; mask always contains bit 0 dp = [INF] * ((1 << n) * n) dp[1 * n + 0] = 0 for mask in range(1, 1 << n): if not (mask & 1): continue base = mask * n for j in range(n): cur = dp[base + j] if cur == INF: continue row = dist[j] for k in range(1, n): bit = 1 << k if mask & bit: continue nm = mask | bit idx = nm * n + k val = cur + row[k] if val < dp[idx]: dp[idx] = val best = INF for j in range(1, n): v = dp[full * n + j] if v == INF: continue v += dist[j][0] if v < best: best = v return int(best)1-е местоGoogle Gemini 3.8 Flashрешено · 9 из 9 тестовответ за 8.6 с · работа 138 мс · $0.0022 ✓ shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])ожидалось 80 2 мс ✓ shortest_tour([[0]])ожидалось 0 1 мс ✓ 2 мс✓ 2 мс✓ <1 мс✓ 1 мс✓ <1 мс⏱ 66 мс⏱ 63 мсКод
def shortest_tour(dist: list[list[int]]) -> int: n = len(dist) if n <= 1: return 0 # DP with bitmask # dp[mask][u]: min cost to start at 0, visit set of cities represented by mask, ending at u. # Cities other than 0 are indexed 1 .. n-1. # mask will represent cities 1 .. n-1 that have been visited. # Total subsets: 1 << (n - 1) num_subsets = 1 << (n - 1) INF = float('inf') dp = [INF] * ((n - 1) * num_subsets) # Base cases: from city 0 to city u (1-indexed, so u-1 in 0..n-2) for u in range(1, n): dp[(1 << (u - 1)) * (n - 1) + (u - 1)] = dist[0][u] for mask in range(1, num_subsets): base_mask = mask * (n - 1) for u in range(1, n): u_idx = u - 1 if not (mask & (1 << u_idx)): continue cur_dist = dp[base_mask + u_idx] if cur_dist == INF: continue # Transition to next city v for v in range(1, n): v_idx = v - 1 if not (mask & (1 << v_idx)): next_mask = mask | (1 << v_idx) idx = next_mask * (n - 1) + v_idx cost = cur_dist + dist[u][v] if cost < dp[idx]: dp[idx] = cost full_mask = num_subsets - 1 base_full = full_mask * (n - 1) ans = INF for u in range(1, n): ans = min(ans, dp[base_full + (u - 1)] + dist[u][0]) return int(ans)
Стоимость токенов: $0.0082 · Как проходят и оцениваются раунды →