68. 최소 비용 (가중치 방향그래프 인접 리스트:vector, STL pair 자료구조)

문제

가중치 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 최소비용을 출력하는 프로그램을 작성하세요.

입력설명

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

출력설명

최소비용을 출력합니다.

입력예제

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 <stdio.h>
#include <vector>
using namespace std;
int check[30], n, cost=2147000000;
vector<pair<int, int> > map[30];

void DFS(int v, int sum){
	if(v == n){
		if(sum < cost){
			cost = sum;
		} 
	} else {
		for(int i=0; i<map[v].size(); i++){
			if(check[map[v][i].first]==0){
				check[map[v][i].first] = 1;
				DFS(map[v][i].first, sum+map[v][i].second);
				check[map[v][i].first] = 0;
			}
		}
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		map[a].push_back(make_pair(b, c));
	}
	check[1] = 1;
	DFS(1, 0);
	printf("%d", cost);
	
	return 0;
}

문제는 같은데 vector객체로 푸냐 배열로 푸냐 pair를 활용해서 푸냐에 따라 코드만 다릅니다