백준 10971 외판원 순회 2

문제 링크: https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

N의 제한이 작기 때문에, next_permutation을 이용하여 모든 가능한 경로에서의 비용을 구하고, 그 비용들의 최소값을 구하면 된다. 한 도시에서 다른 도시로 못가는 경우도 있기때문에 예외처리를 잘 해줘야한다.

#include <bits/stdc++.h>
using namespace std;
 
int n, a[11], w[11][11];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++)
        a[i] = i;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
        cin >> w[i][j];
 
    int ans = 1e9;
    do {
        int sum = w[a[n - 1]][a[0]];
        bool ok = w[a[n - 1]][a[0]] == 0 ? false : true;
        for(int i = 0; i < n - 1; i++) {
            if(w[a[i]][a[i + 1]] == 0) ok = false;
            sum += w[a[i]][a[i + 1]];
        }
        if(ok) ans = min(ans, sum);
    } while(next_permutation(a, a + n));
 
    cout << ans << '\n';
    return 0;
}