54. 최소비용(DFS : 인접행렬)

 

 

▣ 입력예제

 

5 8

1 2 12

1 3 6

1 4 10

2 3 2

2 5 2

3 4 3

4 2 2

4 5 5

 

 

▣ 출력예제

 

13

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int map[30][30], ch[30], n, cost = INT_MAX;

void DFS(int v, int sum)
{
	if (v == n)
	{
		if (sum < cost)
		{
			cost = sum;
		}
	}
	else
	{
		for (int i = 1; i <= n; ++i)
		{
			if (map[v][i] > 0 && ch[i] == 0)
			{
				ch[i] = 1;
				DFS(i, sum + map[v][i]);
				ch[i] = 0;
			}
		}
	}
}

int main()
{
	int m,a,b,c;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		cin >> a>>b>>c;
		map[a][b] = c;
	}
	ch[1] = 1;
	DFS(1,0);
	cout << cost;
}