글 읽기 - 외판원 순회 2 문제 도와주세요 ㅠㅠ

jeoses 6년 전 0

외판원 순회 2 문제 반례가 생각되지 않습니다.

14% 에서 틀렸다고 뜨는데 어디가 문제인지 감이 오지 않습니다....

도와주세요 ㅠㅠ

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, w[11][11], visited[11][11], visited2[11], result, cnt, start, index, *value;
void input()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &w[i][j]);
		}
	}
	int diff = 1;
	for (int i = 1; i <= n - 1; i++)
	{
		diff *= i;
	}
	diff *= n;
	value = new int[diff];
}
void dfs(int a, int b)
{
	if (start == b)
	{
		if (cnt == 3)
		{
			result += w[a][b];
			value[index] = result;
			result -= w[a][b];
			index++;
		}
		return;
	}

	if (visited2[b] != 0 && start != b)
	{
		return;
	}
	for (int i = 0; i < n; i++)
	{
		if (w[b][i] != 0 && !visited[b][i])
		{
			visited[a][b] = visited2[b] = 1;
			result += w[a][b];
			cnt++;
			dfs(b, i);
			result -= w[a][b];
			visited[a][b] = visited2[b] = 0;
			cnt--;
		}

	}

}
void solve()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (w[i][j] != 0)
			{
				result = 0;
				start = i;
				dfs(i, j);
			}
		}
	}
	sort(value, value + index);
}
main()
{
	input();
	solve();
	printf("%d\n", value[0]);
	delete[] value;
}

artage7 6년 전 0

읽어볼 엄두도 안나네요..;

어디서 시작해도 싸이클이라 똑같으니 0에서 시작한다고 하면

모든 경우의 수를 확인합니다. ( 어느 순서대로 방문할지 정하는 거죠 )

예를들어 1->3->4>2 라고 하면 1에서 2까지 가는 코스트 계산하고

마지막에 2->1로 가는 코스트 까지 더해서 저장합니다.

같은 방법으로 모든 방법으로 했을 때 가장 작은것을 출력합니다.

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

문제

문제

출처

ICPC

외판원 순회 2 문제 도와주세요 ㅠㅠ

jeoses 6년 전 0

artage7 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말