글 읽기 - 외판원순회2번 문제 제발 알려주세요.답답해 미치겠습니다..

his130 6년 전 0

코드를 짜봤는데 어디서 틀린지 도대체 모르겠어요...

next_permutation을 통해서 모든경우를 돌리고

체크하는 방법입니다

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N;
vector<int> v[11];
vector<int> s;

int cal()
{
	int sum = 0;

	for (int i = 0; i < N - 1; i++)
	{
		if ( v[s[i]][s[i + 1]] == 0)
		{
			return 2147483647;
		}
		if (v[s[i]][s[i + 1]] != 0)
		{
			sum += v[s[i]][s[i + 1]];
		}
	}
	if (v[N - 1][s[0]] != 0)
	{
		sum += v[s[N - 1]][s[0]];
	}
	
	if (v[N - 1][s[0]] == 0)
	{
		return 2147483647;
	}


	return sum;
}
int main()
{
	cin >> N;

	for (int i = 0; i<N; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		v[i].push_back(a);
		v[i].push_back(b);
		v[i].push_back(c);
		v[i].push_back(d);
	}

	for (int i = 0; i<N; i++)
	{
		s.push_back(i);
	}

	int ans = 2147483647;

	do {
		int temp = cal();
		if (temp<ans)
		{
			ans = temp;
		}
	} while (next_permutation(s.begin(), s.end()));


	cout << ans << endl;
	return 0;
}

rkm0959 6년 전 1

v[i]에 왜 4개의 원소만 들어가죠? n개가 들어가야 하지 않나요?

his130 6년 전 0

감사합니다. 제가 입력하는 값에서 착오를 일으켰네요.

그리고 cal에서 N-1을 s[N-1] 로 바꿔야 헀습니다.

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

문제

문제

출처

ICPC

외판원순회2번 문제 제발 알려주세요.답답해 미치겠습니다..

his130 6년 전 0

rkm0959 6년 전 1

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말