[2/15] Traveling Salesman Problem 1

[spdkimo]

초심자용 문제 - 탐색 http://algospot.com/judge/problem/read/TSP1

문제 ID 시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) TSP1 1000ms 65536kb 551 249 (45%)

[Sprexatura]

제한 시간 초과가 뜨네요-

나중에 다시 디버깅을 해봐야겠습니다.

import sys

from itertools import permutations
def doSolve(cityCost):
    numOfCity = len(cityCost)
    totalPlan = permutations(range(0, numOfCity))
    minCost = sys.maxint
    minPlan = ()
    for plan in totalPlan:
        totalCost = 0.0
        for idx in range(0, len(plan)-1):
            cost = float(cityCost[plan[idx]][plan[idx+1]])
            totalCost = totalCost + cost
        if minCost > totalCost:
            minCost = totalCost
            minPlan = plan
    return minCost

NumberOfTestcase = int(raw_input())
answerList = []
TestcaseNumber = 0
while NumberOfTestcase > TestcaseNumber:
    NumberOfCity = int(raw_input())
    cityCost = [[0 for col in range(NumberOfCity)] for row in range(NumberOfCity)]

    for lineNum in range(0, NumberOfCity):
        cityCost[lineNum] = raw_input().split()
    answerList.append(doSolve(cityCost))
    TestcaseNumber = TestcaseNumber+1

for result in answerList: print result

[Sprexatura]

문제 검증에 도움되시라고 작은 데이터 셋 공유합니다.

cityCost_8 = [[0,29,82,46,68,52,72,42],
              [29,0,55,46,42,43,43,23],
              [82,55,0,68,46,55,23,43],
              [46,46,68,0,82,15,72,31],
              [68,42,46,82,0,74,23,52],
              [52,43,55,15,74,0,61,23],
              [72,43,23,72,23,61,0,42],
              [42,23,43,31,52,23,42,0]]

cityCost_15 = [[0,29,82,46,68,52,72,42,51,55,29,74,23,72,46],
               [29,0,55,46,42,43,43,23,23,31,41,51,11,52,21],
               [82,55,0,68,46,55,23,43,41,29,79,21,64,31,51],
               [46,46,68,0,82,15,72,31,62,42,21,51,51,43,64],
               [68,42,46,82,0,74,23,52,21,46,82,58,46,65,23],
               [52,43,55,15,74,0,61,23,55,31,33,37,51,29,59],
               [72,43,23,72,23,61,0,42,23,31,77,37,51,46,33],
               [42,23,43,31,52,23,42,0,33,15,37,33,33,31,37],
               [51,23,41,62,21,55,23,33,0,29,62,46,29,51,11],
               [55,31,29,42,46,31,31,15,29,0,51,21,41,23,37],
               [29,41,79,21,82,33,77,37,62,51,0,65,42,59,61],
               [74,51,21,51,58,37,37,33,46,21,65,0,61,11,55],
               [23,11,64,51,46,51,51,33,29,41,42,61,0,62,23],
               [72,52,31,43,65,29,46,31,51,23,59,11,62,0,59],
               [46,21,51,64,23,59,33,37,11,37,61,55,23,59,0]]