टास्क · एल्गोरिदम कठिन Python ·

Shortest round trip

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

• #1OpenAI GPT-5.3-Codexहल किया गया · 9 में से 9 टेस्ट्स पासजवाब का समय 4.0 s · रनटाइम 95 ms · $0.0054

  ✓	shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])अपेक्षित 80	<1 ms
  ✓	shortest_tour([[0]])अपेक्षित 0	1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 49 ms⏱ 40 ms
  कोड

  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 ms · रनटाइम 109 ms · $0.0002

  ✓	shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])अपेक्षित 80	<1 ms
  ✓	shortest_tour([[0]])अपेक्षित 0	3 ms

  ✓ 3 ms✓ <1 ms✓ <1 ms✓ 3 ms✓ <1 ms⏱ 53 ms⏱ 45 ms
  कोड

  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 s · रनटाइम 132 ms · $0.0004

  ✓	shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])अपेक्षित 80	4 ms
  ✓	shortest_tour([[0]])अपेक्षित 0	3 ms

  ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms⏱ 64 ms⏱ 55 ms
  कोड

  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 s · रनटाइम 138 ms · $0.0022

  ✓	shortest_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])अपेक्षित 80	2 ms
  ✓	shortest_tour([[0]])अपेक्षित 0	1 ms

  ✓ 2 ms✓ 2 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 66 ms⏱ 63 ms
  कोड

  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 · राउंड कैसे आयोजित और स्कोर किए जाते हैं →