BOJ 외판원 순회 2 - 10971번

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

10971번: 외판원 순회 2

 

 

//나머지
#include<stdio.h>
#include<vector>
#include<stack>
#include<string.h>
#include<algorithm>
using namespace std;

int main(void)
{
    int n;
    int w[10][10] = {0, };
    int a[10];
    int min=2100000000;

    for(int i=0; i<10; i++)
    {
        a[i] = i;
    }
    int sum=0;

    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            scanf("%d", &w[i][j]);
        }
    }
    do{
        sum=0;
        int flag = 1;
        for(int i=0; i<n; i++)
        {
            int x;
            if(i+1 < n)
            {
                x = w[a[i]][a[i+1]];
                sum+=x;
            }
            else
            {
                x = w[a[i]][a[0]];
                sum+=x;
            }
            if(x==0)
            {
                flag++;
            }
        }
        if(flag == 1 && min>sum)
        {
            min = sum;
        }
    }while(next_permutation(a, a+n)!=0);

    printf("%d", min);
	return 0;
}