68. 최소비용(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,ch[30],cost=2147000000;
vector<pair<int, int> > map[30];
void DFS(int v,int sum){
int i;
if(v==n){
if(sum<cost) cost=sum;
}
else {
for(i=0;i<map[v].size();i++){
if(ch[map[v][i].first]==0){
ch[map[v][i].first]=1;
DFS(map[v][i].first,sum+map[v][i].second); //map[v][i].first 는 노드 map[v][i].second는 가중치
ch[map[v][i].first]=0;
}
}
}
}

int main() {

int m,a,b,c,i;
cin>>n>>m;
for(i=1;i<=m;i++){
	cin>>a>>b>>c;
	map[a].push_back(make_pair(b,c)); // a ㅁㅁ ㅁ-----ㅁㅁ ㅁ
	
}

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

return 0;

}