2098번: 외판원 순회 - DP(비트마스킹)

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

2098번: 외판원 순회

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int N;
int W[16][16];
int dp[65536][16];
int node{ 0 };

void f(int idx, int cnt, int bit)
{
	if (cnt == 0)
	{
		for (int i{ 0 }; i < N; i++) //i : 도착 도시
		{
			if (node < N && i == 0) continue; 
			//전부 순회할 때까지 도시 0으로 가지 않는다.

			if ((idx | (1 << i)) == idx) //도시들 중 도착 도시가 있다면
			{
				int x{ idx & ~(1 << i) }; //지금까지 여행한 도시들
				for (int j{ 0 }; j < N; j++) //j : 출발 도시
				{
					if (dp[x][j] == inf || W[j][i] == 0) continue;
					//지금까지 여행한 도시들의 도착 도시가 j가 아니면 무시
					//갈 수 없는 경로면 무시
					dp[idx][i] = min(dp[idx][i], dp[x][j] + W[j][i]);
				}
			}
		}
		return;
	}

	for (int i{ bit }; i < N; i++)
	{
		f(idx + (1 << i), cnt - 1, i + 1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i{ 0 }; i < N; i++)
	{
		for (int j{ 0 }; j < N; j++)
		{
			cin >> W[i][j];
		}
	}
	for (int i{ 0 }; i < pow(2, N); i++)
	{
		for (int j{ 0 }; j < N; j++)
		{
			dp[i][j] = inf; //dp 초기화
		}
	}
	dp[0][0] = 0; //시작 도시는 0

	for (int i{ 1 }; i <= N; i++)
	{
		node++;
		f(0, i, 0);
	}
	cout << dp[(1 << N) - 1][0];
}