글 읽기 - (c++) 16118.달빛 여우 문제 여러 번 도전해봐도 메모리 초과가 됩니다.

i_am_commang 2년 전 0

지금은 이 문제를 여우는 그냥 다익스트라를 돌리고

늑대는 1번째 그루터기에서 a번째로 간다고 했을 때

1번에서 빠르게 가면 1번에서 a+n으로 가고, 느리게 간다고 하면 1+n에서 a로 가도록

즉 빠르게 가는 상황이면 1 ~ n번에서 가고 느리게 가는 상황이면 1+n ~ 2n에서 가도록

그래프를 다시 만들고 다익스트라를 돌렸습니다.

무엇인가 제가 모르는 작은 실수인가 해서 조금씩 바꾸기도 해보고

알고리즘이 이상한가 해서 처음의 방법인 하나의 그래프에서 늑대의 상태만 바꿔가면서 다익스트라 도는 방법에서

지금의 방법으로 바꾸기도 해보았습니다.

하지만 계속 메모리 초과가 됩니다...

어디에서 문제가 생겼는지 아니면 간단한 추측, 힌트라도 알려주실 수 있으신가요?ㅠㅠ..

#include <iostream>
#include <queue>

using intPair = std::pair<int,int>;	//cost / to


std::vector<intPair> graph[4001];
std::vector<intPair> wolfGraph[8001];	//시작이 1~n 빠르게 감, 시작이 n+1~2n 느리게 감(1, n)
int fox[4001], wolf[8001];

void dijk(int* arr, std::vector<intPair>* _graph) {
	std::priority_queue<intPair, std::vector<intPair>, std::greater<intPair>> pq;
	arr[1] = 0;
	pq.push(intPair(0,1));

	intPair cur;
	while (!pq.empty()) {
		cur = pq.top(); pq.pop();

		if (cur.first > arr[cur.second]) continue;

		for (const intPair& next : _graph[cur.second]) {
			if (next.first + cur.first > arr[next.second]) continue;

			arr[next.second] = next.first + cur.first;
			pq.push(intPair(arr[next.second], next.second));
		}

	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n, m;
	std::cin >> n >> m;

	for (int i = 0, from, to, c; i < m; i++) {
		std:: cin >> from >> to >> c;
		graph[from].push_back(intPair(c*2, to));
		graph[to].push_back(intPair(c*2, from));

		wolfGraph[from].push_back(intPair(c, n + to));
		wolfGraph[n + to].push_back(intPair(c * 4, from));
		wolfGraph[n + from].push_back(intPair(c * 4, to));
		wolfGraph[to].push_back(intPair(c, n + from));
	}

		
	for (int i = 1; i <= n; i++) fox[i] = wolf[i] = wolf[n+i] = 2e9;

	//fox
	dijk(fox, graph);

	//wolf
	dijk(wolf, wolfGraph);

	//for (int i = 1; i <= n; i++) {
	//	std::cout << i<<" / fox :" << fox[i] << " wolf[1] :" << wolf[i] << " wolf[0] :" << wolf[n+i] << "\n";
	//}
	
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		if(fox[i] < std::min(wolf[i], wolf[n+i]))cnt++;
	}

	std::cout << cnt;
	return 0;
}

woolim 2년 전 1

확실하진 않지만 23번줄에 if 조건문이 next.first + cur.first > arr[next.second] 이여서

next.first + cur.first == arr[next.second] 인 경우에 실제로 distance가 업데이트 되지 않지만 pq가 쌓여서 메모리초과가 나는것 같아요

23번줄을 next.first + cur.first >= arr[next.second] 로 바꿔보세요

i_am_commang 2년 전 0

와ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

선생님 감사합니다ㅠㅠㅠㅠ;;

다익스트라 문제를 오랜만에 푸는데

다음에 갈 노드 찾는 걸 항상 next.first + cur.first > arr[next.second]라고만 했던 것 같아서

그쪽 조건문은 안보고 있었는데....

=하나 때문에 계속 메모리가 쌓이고 있었네요, 다음부터 이런 실수 하지 않겠습니다;;;

정말로 감사합니다!!!!!!!

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

문제

문제

출처

ICPC

(c++) 16118.달빛 여우 문제 여러 번 도전해봐도 메모리 초과가 됩니다.

i_am_commang 2년 전 0

woolim 2년 전 1

i_am_commang 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말