https://www.acmicpc.net/problem/10971
10971번: 외판원 순회 2
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다.
www.acmicpc.net
|
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
74
75
76
77
78
79
80
81
82
|
#include <iostream>
#include <vector>
int arr[11][11];
bool check[11];
int n;
int minimum_dist = 987654321;
void input()
{
std::cin >> n;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
std::cin >> arr[i][j];
}
}
}
bool GetAllChk()
{
for (int i = 1; i <= n; ++i)
{
if (check[i] == false)
{
return false;
}
}
return true;
}
void dfs(int route, int stk, int dist)
{
if (stk == n - 1)
{
if (arr[route][1] != 0)
{
if (dist + arr[route][1] < minimum_dist)
{
minimum_dist = dist + arr[route][1];
}
}
return;
}
for (int i = 2; i <= n; ++i)
{
if (check[i] != true && arr[route][i] != 0)
{
check[i] = true;
dfs(i, stk + 1, dist + arr[route][i]);
check[i] = false;
}
}
}
void solve()
{
dfs(1, 0, 0);
}
void output()
{
if (minimum_dist == 987654321)
{
std::cout << 0;
return;
}
std::cout << minimum_dist;
}
int main()
{
input();
solve();
output();
return 0;
}
|
cs |
http://www.koistudy.net/?mid=prob_page&NO=706&SEARCH=0
www.koistudy.net
|
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
|
#include <stdio.h>
int n, m, G[11][11], sol = 0x7fffffff, chk[11];
void solve(int V, int W)
{
if (V == n)
{
if (W < sol)
{
sol = W;
}
return;
}
for (int i = 1; i <= n; ++i)
{
if (!chk[i] && G[V][i])
{
chk[i] = 1;
solve(i, W + G[V][i]);
chk[i] = 0;
}
}
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i)
{
int s, e, w;
scanf("%d %d %d", &s, &e, &w);
G[s][e] = G[e][s] = w;
}
solve(1, 0);
printf("%d\n", sol == 0x7fffffff ? -1 : sol);
return 0;
}
|
cs |
|
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>
int arr[11][11];
bool check[11];
int n, m;
int minimum_dist = 987654321;
void input()
{
std::cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int u, v, val;
std::cin >> u >> v >> val;
arr[u][v] = val;
arr[v][u] = val;
}
}
void dfs(int route, int end, int dist)
{
if (route == end)
{
if (dist < minimum_dist)
{
minimum_dist = dist;
}
return;
}
for (int i = 1; i <= end; ++i)
{
//arr[route][i] 는 항상 값이 0이니 i == route는 필요 없다
if (i == route || check[i] == true)
{
continue;
}
if (arr[route][i] != 0)
{
check[i] = true;
dfs(i, end, dist + arr[route][i]);
check[i] = false;
}
}
}
void solve()
{
check[1] = true;
dfs(1, n, 0);
}
void output()
{
std::cout << minimum_dist;
}
int main()
{
input();
solve();
output();
return 0;
}
|
cs |
방법은 거의 똑같다
'알고리즘' 카테고리의 다른 글
| 백준 2023 : 신기한 소수 & koi 절단 가능 소수 (0) | 2020.04.25 |
|---|---|
| koi : 리모콘(dfs, bfs) (0) | 2020.04.24 |
| 백준 2615 : 오목 (0) | 2020.04.20 |
| 백준 7573 : 고기잡이 (0) | 2020.04.20 |
| 백준 2622 : 삼각형 만들기 (0) | 2020.03.28 |