Hadongspapa: TSP 구현

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
#define    INF 987654321
#define MAX_N 6
int N, Graph[MAX_N][MAX_N];
int solve(int pos, int  visited);
 
int solve(int pos, int visited)
{
    if (visited == (1 << N) - 1)
        return 0;
 
    int ret = INF;
    for (int next = 0; next < N; ++next)
    {
        if (!(visited & (1 << next)) && Graph[pos][next])
        {
            int tmp = Graph[pos][next] + solve(next, visited | (1 << next));
            if (tmp < ret)
                ret = tmp;
        }
    }
 
    return ret;
}
 
int main()
{
    int tcCnt;
    freopen("tsp_input.txt", "r", stdin);
    cin >> tcCnt;
    for (int t = 1; t <= tcCnt; ++t)
    {
        cin >> N;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                cin >> Graph[i][j];
 
        int ans = INF;
        for (int i = 0; i < N; ++i)
        {
            int tmp = solve(i, 1 << i);
            if (ans > tmp) ans = tmp;
        }
        cout << "#" << t << ' ' << ans << endl;
    }
    return 0;
}
Colored by Color Scripter
cs
Colored by Color Scripter
Hadongspapa

2018년 7월 31일 화요일

TSP 구현 - 1

댓글 없음:

댓글 쓰기
