글 읽기 - 외판원 순회2 반례 부탁드립니다.

rlaehdgkr7 4년 전 0

백준 선생님 인강을 듣고 있는 학생입니다.

외판원 순회2 문제를 풀고 있는데 제 코드에 예시를 넣어보니 작동하는데 채점할 땐 틀리다고 나오네요.

제가 아직 적당한 반례를 찾지 못하는것 같은데 반례 하나만 알려주실 수 있을까요?

혹은 코드에서 어느 부분이 잘못된 건지 알려주시면 감사하겠습니다.

현재 "외판원순회2" 문제의 질문게시판에 있는 질문들의 답변 반례들은 거의 다 넣어본 상황입니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
int main() {
	int n;
	int tot_cost = 0, min_cost = 100000;
	cin >> n;
	vector <int> perm(n);
	for (int i = 0; i < n; i++) {
		perm[i] = i; // 0 1 2 3 
	}

	// 2-dim cost allocation
	int** cost = new int* [n];
	for (int i = 0; i < n; ++i) {
		cost[i] = new int[n];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> cost[i][j];
		}
	}
	do {
		for (int i = 0; i < n; i++) {
			tot_cost += cost[perm[i]][perm[(i + 1) % n]];
		}

		min_cost = min(min_cost, tot_cost);
		tot_cost = 0;
	} while (next_permutation(perm.begin(), perm.end()));
	if (min_cost == 0) {
		return 1;
	}
	else {
		cout << min_cost;
		return 0;
	}
}

shiftpsh 4년 전 1

행렬의 성분이 0인 경우는 갈 수 없는 경우입니다.

rlaehdgkr7 4년 전 1

감사합니다! 해결했습니다^^

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

문제

문제

출처

ICPC

외판원 순회2 반례 부탁드립니다.

rlaehdgkr7 4년 전 0

shiftpsh 4년 전 1

rlaehdgkr7 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말