외판원 순회 2

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다.

단, 한 번 갔던 도시로는 다시 갈 수 없다. 

고로, 순열을 이용할 수 있는데?!

N 제한을 봐야한다! 시간 초과를 생각해야하기 때문...

N 제한이 10이다! ㄱㄴ

O(N * N!)

#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;
}