67. 최소 비용 (그래프 DFS)

나의정답.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int map[30][30];
int cp[30] = { 0 };
int n, sum = 0;
int mi = 100000;

void dfs(int v) {
if (v == n) {
	if (sum < mi) 
		mi = sum;
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (map[v][i] == 0) continue;
			if (cp[i] == 1) continue;

			cp[i] = 1;
			sum += map[v][i];
			dfs(i);
			sum -= map[v][i];
			cp[i] = 0;
		}
	}
}

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int m, a, b, c;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < 30; i++)
		for (int j = 0; j < 30; j++)
			map[i][j] = 0;

	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		map[a][b] = c;
	}

	cp[1] = 1;
	dfs(1);
	printf("%d", mi);
}