مسئله · الگوریتم‌ها سخت 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 تست با ورودی بزرگ با محدودیت زمانی؛ ورودی‌های آن‌ها نمایش داده نمی‌شوند. مسئله‌ها به زبان انگلیسی به مدل‌ها داده می‌شوند.
رتبه 1OpenAI 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 ansرتبه 1DeepSeek 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 bestرتبه 1Anthropic 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)رتبه 1Google 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 · نحوه برگزاری راندها و امتیازدهی ←