뚝배기 터진 문제_boj
boj 2098 외판원 순회
헐랭미
2020. 7. 2. 15:01
https://www.acmicpc.net/problem/2098
풀 수 있었는데 결국에는 못풀었다. 흑흑
다 왔는데 또또또또또또 문제를 완벽히 읽지 않아서 질문게시판의 TC를 참고해 버렸다.
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define pii pair<int, int>
#define FULL 65536
#define INF 987654321
using namespace std;
int d[16][FULL];
int arr[16][16];
int n;
//visit이 0이면 방문, 1이면 방문 X
int go(int cur, int visit)
{
if (visit == (1 << n) - 1)
return d[cur][visit] = arr[cur][0];
if (d[cur][visit] != INF)
return d[cur][visit];
for (int i = 0; i < n; i++)
{
if (((visit & 1 << i) != 0) || cur == i)
continue;
int n_visit = visit + (1 << i);
d[cur][visit] = min(d[cur][visit], arr[cur][i] + go(i, n_visit));
}
return d[cur][visit];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> arr[i][j];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < (1<<n); j++)
d[i][j] = INF;
}
cout << go(0, 1);
/*
cout << "???? "<< go(0, 1) << '\n';
for (int i = 0; i < n; i++)
{
for (int j = 0; j < (1 << n); j++)
cout << d[i][j] << ' ';
cout << '\n';
}
*/
}
|
cs |
이것이 직전의 소스인데
문제 지문 중에 -> 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.
라는것을 파악하지 못했다. 그래서 그것을 수정하니 정답이 나왔다.
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define pii pair<int, int>
#define FULL 65536
#define INF 987654321
using namespace std;
int d[16][FULL];
int arr[16][16];
int n;
//visit이 0이면 방문, 1이면 방문 X
int go(int cur, int visit)
{
if (visit == (1 << n) - 1)
{
if(arr[cur][0] != 0)
return d[cur][visit] = arr[cur][0];
}
if (d[cur][visit] != INF)
return d[cur][visit];
for (int i = 0; i < n; i++)
{
if (((visit & 1 << i) != 0) || cur == i || arr[cur][i] == 0)
continue;
int n_visit = visit + (1 << i);
d[cur][visit] = min(d[cur][visit], arr[cur][i] + go(i, n_visit));
}
return d[cur][visit];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> arr[i][j];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < (1<<n); j++)
d[i][j] = INF;
}
cout << go(0, 1);
/*
cout << "???? "<< go(0, 1) << '\n';
for (int i = 0; i < n; i++)
{
for (int j = 0; j < (1 << n); j++)
cout << d[i][j] << ' ';
cout << '\n';
}
*/
}
|
cs |