โจทย์ · อัลกอริทึม ยาก 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 · วิธีจัดการแข่งขันและการคิดคะแนน →