글 읽기 - 제 비쥬얼스튜디오에서는 잘만되는데.. 바로 틀렸습니다가 나올까요 ?

bbomi1458 3년 전 0

책보면서 완전탐색으로 코드를 작성해봤는데요.

채점중에 그냥 바로 틀렸습니다가 뜨는데,

정말 모르겠네요

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int dist[10][10];

int shortestPath(vector<int>& path, vector<bool>& visited, int currentLength) {

	if(path.size() == n) {
		if(dist[path.back()][path[0]]!=0)
			return (currentLength + dist[path.back()][path[0]]);
		return 0;
	}

	int ret = 100000000;
	
	for (int next = 0; next < n; ++next) {
		if (visited[next]) continue;
		int here = path.back();
		if (dist[here][next] == 0) continue;
		path.push_back(next);
		visited[next] = true;
		int cand = shortestPath(path, visited, currentLength + dist[here][next]);

		ret = min(ret, cand);
		
		visited[next] = false;
		path.pop_back();
	}
	return ret;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++)
			cin >> dist[i][j];
	
	vector<int> path; vector<bool> visited(n);

	int ret;
	int max = 100000000;
	for (int i = 0; i < n; ++i) {
		path.push_back(i);
		visited[i] = true;
		ret=shortestPath(path, visited, 0);

		max = min(ret, max);
		
		path.pop_back(); visited[i] = false;
			
	}
	cout << max<<endl;
	
}

zlzmsrhak 3년 전 1

반례입니다. 확인해보세요.

bbomi1458 3년 전 0

반례를 주셔서 정말 감사합니다.

그런데 주신 반례가 도시를 다 방문하고 원래 도시로 돌아올때 방문했던 도시를 지나지 않나요?...

제가 문제를 잘못이해한건가요.....

돌아올 때는 지났던 도시를 돌아와도 상관이 없는건가요???...

zlzmsrhak 3년 전 2

반례 작성에 실수가 있었네요. 수정된 반례입니다.

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

문제

문제

출처

ACM-ICPC

제 비쥬얼스튜디오에서는 잘만되는데.. 바로 틀렸습니다가 나올까요 ?

bbomi1458 3년 전 0

zlzmsrhak 3년 전 1

bbomi1458 3년 전 0

zlzmsrhak 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말