10971번: 외판원 순회 2
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int w[20][20];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&w[i][j]);
}
}
vector<int> d(n);
for (int i=0; i<n; i++) {
d[i] = i;
}
int ans=2147483647;
do {
bool ok = true;
int sum = 0;
for (int i=0; i<n-1; i++) {
if (w[d[i]][d[i+1]] == 0) {
ok = false;
} else {
sum += w[d[i]][d[i+1]];
}
}
if (ok && w[d[n-1]][d[0]] != 0) {
sum += w[d[n-1]][d[0]];
if (ans > sum) ans = sum;
}
} while (next_permutation(d.begin(), d.end()));
printf("%d\n",ans);
return 0;
}
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[20][20];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
vector<int> d(n);
for (int i=0; i<n; i++) {
d[i] = i;
}
int ans=2147483647;
do {
bool ok = true;
int sum = 0;
for (int i=0; i<n-1; i++) {
if (a[d[i]][d[i+1]] == 0) {
ok = false;
} else {
sum += a[d[i]][d[i+1]];
}
}
if (ok && a[d[n-1]][d[0]] != 0) {
sum += a[d[n-1]][d[0]];
if (ans > sum) ans = sum;
}
} while (next_permutation(d.begin()+1, d.end()));
printf("%d\n",ans);
return 0;
}'Problem set' 카테고리의 다른 글
| [백준] 9095 1, 2, 3 더하기 (0) | 2021.02.20 |
|---|---|
| [백준] 6603 로또 (0) | 2021.01.21 |
| [백준] 10819 차이를 최대로 (0) | 2021.01.21 |
| [백준] 10974 모든 순열 (0) | 2021.01.21 |
| [백준] 10973 이전 순열 (0) | 2021.01.21 |