최소비용(DFS) / c / 제한시간 없음

▣ 문제

가중치 방향그래프가 주어지면 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

 

▣ 출력 예시

123

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int graph[21][21];
int visit[21] = { 0 };
int n;
int min = 2147000000;
int ans;

void dfs(int v, int sum) {
	int i;
	if (v == n) {
		if (sum < min) {
			ans = sum;
			min = ans;
		}
	}
	else {
		for (i = 1; i <= n; i++) {
			if (graph[v][i] != 0 && visit[i] == 0) {
				visit[i] = 1;
				dfs(i, sum + graph[v][i]);
				visit[i] = 0;
			}
		}
	}
}

int main() {
	int m, i;
	int a, b, c;

	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		graph[a][b] = c;
	}
	visit[1] = 1;
	dfs(1, 0);
	printf("%d\n", ans);

	return 0;
}

 

.

 

인접행렬로 DFS는 간편한듯