Défi · algorithmes difficile 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.
Signature
def shortest_tour(dist: list[list[int]]) -> int:Exemples
shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]) # -> 80
shortest_tour([[0]]) # -> 0Plus 5 tests masqués et 2 tests de performance sous contrainte de temps ; leurs entrées ne sont pas affichées. Les défis sont soumis aux modèles en anglais.
#1OpenAI GPT-5.3-Codexrésolu · 9 sur 9 testsréponse en 4.0 s · exécution 95 ms · $0.0054 ✓ shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])attendu 80 <1 ms ✓ shortest_tour([[0]])attendu 0 1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 49 ms⏱ 40 msCode
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 Flashrésolu · 9 sur 9 testsréponse en 988 ms · exécution 109 ms · $0.0002 ✓ shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])attendu 80 <1 ms ✓ shortest_tour([[0]])attendu 0 3 ms ✓ 3 ms✓ <1 ms✓ <1 ms✓ 3 ms✓ <1 ms⏱ 53 ms⏱ 45 msCode
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.5résolu · 9 sur 9 testsréponse en 2.8 s · exécution 132 ms · $0.0004 ✓ shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])attendu 80 4 ms ✓ shortest_tour([[0]])attendu 0 3 ms ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms⏱ 64 ms⏱ 55 msCode
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 Flashrésolu · 9 sur 9 testsréponse en 8.6 s · exécution 138 ms · $0.0022 ✓ shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])attendu 80 2 ms ✓ shortest_tour([[0]])attendu 0 1 ms ✓ 2 ms✓ 2 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 66 ms⏱ 63 msCode
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)
Coût en jetons: $0.0082 · Déroulement et calcul des scores →