글 읽기 - 메모리초과 질문드립니다

sjnam07 5년 전 0

아래 코드를 올리면 메모리초과가 나옵니다. Edge와 Vertex를 최대치로 한 여러 케이스를 돌려도 최대 28MB만 나오는데, 어디서 잘못된지 모르겠네요ㅜ

도움 부탁 드립니다.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <utility>
#include <bitset>
#include <queue>
#include <functional>

#define _INF	(1000000000)
#define _MAX_E	(300000)

using namespace std;

typedef pair<int, int> distPair;

class Graph
{
public:
	Graph() {}
	~Graph() {}

	void GetInput(void)
	{
		int v;
		int e;
		int start;
		int end;
		int dist;

		cin >> v >> e >> m_nStart;

		m_AdjList.resize(v);
		m_MinTable.resize(v, _INF);

		for (int i = 0; i < e; i++) {
			cin >> start >> end >> dist;
			m_AdjList[start - 1].push_back(distPair(dist, end - 1));
		}
		m_nStart--;//Set to zero base
	}

	void Solve(void)
	{
		Dijkstra(m_nStart);

		for (size_t i = 0; i < m_MinTable.size(); i++) {
			if (m_MinTable[i] != _INF) {
				cout << m_MinTable[i] << endl;
			}
			else {
				cout << "INF" << endl;
			}
		}
	}

private:
	vector<list<distPair>> m_AdjList;
	vector<int> m_MinTable;
	int m_nStart;

	int GetDist(const distPair &d) {
		return d.first;
	}

	int GetPoint(const distPair &d) {
		return d.second;
	}

	void Dijkstra(int start) {
		priority_queue< distPair, vector<distPair>, greater<distPair> > q;
		bitset<_MAX_E> visited;

		m_MinTable[start] = 0;
		q.push(distPair(0, start));

		while (!q.empty()) {
			int point = GetPoint(q.top());
			int dist = GetDist(q.top());
			q.pop();

			if (dist >= _INF || dist > m_MinTable[point]) {
				continue;
			}

			visited[point] = true;

			// Update minimum table to adjacant points
			for (auto &edge : m_AdjList[point]) {
				int d = GetDist(edge);
				int p = GetPoint(edge);

				int newVal = d + dist;
				if (newVal < m_MinTable[p]) {
					m_MinTable[p] = newVal;
				}

				if (!visited[p]) {
					q.push(distPair(m_MinTable[p], p));
				}
			}
		}
	}
};

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);

	Graph g;
	g.GetInput();
	g.Solve();

    return 0;
}

hyunynim 5년 전 0

질문 올리시기 전에 질문 게시판 공지사항을 한번 보시는게 좋을 듯 합니다.

어떤 의도로 vector안에 다시 list<pair>를 넣어놓으신 건지는 모르곘지만

인접 리스트를 사용할 때 vector 또는 list를 사용합니다.

sjnam07 5년 전 0

특정 정점에 대해 인접한 간선의 정보를 pair<가중치, 연결된 정점>의 list로 표현 한 것입니다.

위 인접리스트를 해당하는 정점에 넣어놓기 위해 vector를 사용한 것이고요.

이 때 공간은 V + E 정도만 차지할 것이고, 최대 정점 20000개 + 간선 300000개를 저장할 공간만 차지하니 128MB가 초과하지 않을 것 같은데요.

혹시 이것에 대해 오류가 있는지요? 뭔가 틀렸으니 답이 안맞는 것일텐데, 도통 찾아지질 않네요. 오류가 있다면 알려주시면 감사하겠습니다.

ybnormal81 5년 전 1

void Dijkstra(int start) {

priority_queue< distPair, vector, greater > q;
bitset<_MAX_E> visited;

m_MinTable[start] = 0;
q.push(distPair(0, start));

while (!q.empty()) {
int point = GetPoint(q.top());
int dist = GetDist(q.top());
q.pop();

for (auto &edge : m_AdjList[point]) {
int d = GetDist(edge);
int p = GetPoint(edge);

int newVal = d + dist;
if (newVal < m_MinTable[p]) {
m_MinTable[p] = newVal;
q.push(distPair(m_MinTable[p], p));
}

}
}
}
};

sjnam07 5년 전 0

어디선가 무한루프 돌아서 큐에 비지못하고 쌓아만 지는 경우가 생기는가 봅니다.ㅠㅠ

답변 감사합니다!

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

문제

문제

출처

ICPC

메모리초과 질문드립니다

sjnam07 5년 전 0

hyunynim 5년 전 0

sjnam07 5년 전 0

ybnormal81 5년 전 1

sjnam07 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말