المهمة · خوارزميات صعب 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 اختبارات مخفية واختباري مدخلات ضخمة ضمن حد زمني؛ لا تُعرض مدخلاتها. تُقدَّم المهام للنماذج باللغة الإنجليزية.
المركز 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 · كيف تُدار الجولات وتُحتسب النقاط ←