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

▣ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연
결정보가 주어진다.
▣ 출력설명
최소비용을 출력합니다.
▣ 입력예제 1
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
▣ 출력예제 1
13

#include
#include
using namespace std;
int n,map[30][30],ch[30],cost=2147000000;
void DFS(int v,int sum){
int i;
if(v==n){ //종료지점
if(sum<cost) cost=sum;
}
else {
for(i=1;i<=n;i++){
if(map[v][i]>0 && ch[i]==0){
ch[i]=1;
DFS(i,sum+map[v][i]); //i는 향하는 노드 map[v][i]는 가중치
ch[i]=0;
}
}
}
}

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

ch[1]=1;
DFS(1,0);
cout<<cost;


return 0;

}