글 읽기 - 외판원문제2 어디가 틀린걸까요.......

jh1125kr 7년 전 0

n이 10이라 dp로 안하고, 완전탐색으로 짰는데요.

어디서 틀렸는지 모르겠습니다..

갈수없는 0도 처리를 해줬고..뭐가 문제일까요 ㅠㅠ

#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<memory.h>
#include<algorithm>
#define INF 2e9
#define ll long long
using namespace std;
int n, start_v, cost;
int v[11][11];
bool visited[11];
int mn = INF;
void dfs(int pre_v, int cnt) 
{
	if (cnt == n)
	{
		cost += v[pre_v][start_v];
		if (cost < mn)
		{
			mn = cost;
		}
		cost -= v[pre_v][start_v];
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (visited[i] == true) continue;
		if (cnt == 0) {
			visited[i] = true;
			start_v = i;
			cost = 0;
			dfs(i, cnt + 1);
		}
		else
		{
			int cur_v = i;
			if (v[pre_v][cur_v] == 0) {
				continue;
			}
			visited[i] = true;
			cost += v[pre_v][cur_v];
			dfs(i, cnt + 1);
			cost -= v[pre_v][cur_v];
		}
		visited[i] = false;
	}
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			scanf("%d", &v[i][j]);
		}
	}
	dfs(0, 0);
	printf("%d\n", mn);
}

jh1125kr 7년 전 1

아 마지막에 0처리를 빼먹었네요

1->3->2->1

2->1일때도 0처리를 해줬어야했는데

해결됐습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

외판원문제2 어디가 틀린걸까요.......

jh1125kr 7년 전 0

jh1125kr 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말