11763.전자키트11763.전자키트

황성안 2021. 4. 15. 10:00
728x90
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
'''
1
3
0 18 34
48 0 55
18 7 0
TSP문제
'''
def perm(n, k, cursum): # 원소의 수 뎁스
    global ans
 
    #가지치기하려면 여기다 넣어야함
    # if ans < cursum : return 내가가진값보다 니가커? 그럼 가지처버렷
    if n == k:
        cursum += dist[t[N-1]][t[N]]
        if ans > cursum: ans = cursum
    else:
        for i in range(n):
            if visited[i+1] : continue
            t[k+1] = a[i+1]
            visited[i+1] = True
            perm(n, k+1, cursum + dist[t[k]][t[k+1]])
            visited[i+1] = False
 
T=int(input())
for tc in range(1, T+1):
    ans = 987654321
    N = int(input())
    a = list(range(N)) # 0 1 2
    #a = [list(map(int,input().split())) for _ in range(N)]
    t = [0] * N + [0] #  0 1 2 0 으로 저장 ( 출발, 도착, 고정)
    visited = [0] * N
    dist = [list(map(int,input().split())) for _ in range(N)]
 
    perm(N-1, 0,0 ) # N - 1 : 0번 인덱스는 제외
    print("#{} {}".format(tc, ans))
cs
728x90