글 읽기 - 메모리초과가 발생합니다.

skynet0149 5년 전 0

한 25%에서 메모리 초과가 발생하는데 어디 부분을 줄여야 될지 모르겠습니다...

dist같은 배열을 vector<int> dist(N, 499000) 이런식으로 초기화를 시켜서 N만큼만 생성해도 똑같이 메모리 초과가 발생합니다...

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int N, M;
int S, D;

struct Pos {
	int  v, p;
	Pos() { v = p = 0; }
	Pos(int b, int c) {
		v = b;
		p = c;
	}
};

struct cmp{
	bool operator()(Pos a, Pos b) {
		return a.p < b.p;
	}
};

vector<Pos> adj[500];
vector<Pos> trace[500];
int dist[500];

void dijkstra() {
	for (int i = 0; i < N; i++)
		dist[i] = 499000;

	priority_queue<Pos, vector<Pos>, cmp> pq;
	Pos t(S, 0);
	pq.push(t);

	while (!pq.empty()) {
		int here = pq.top().v;
		int cost = pq.top().p;
		pq.pop();
		if (dist[here] < cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].v;
			int ncost = cost + adj[here][i].p;

			if (adj[here][i].p == -1)
				continue;

			if (dist[there] > ncost) {
				dist[there] = ncost;
				Pos p(there, ncost);
				pq.push(p);
				p.v = here;
				trace[there].clear();
				trace[there].push_back(p);
			}
			else if (dist[there] == ncost) {
				Pos p(here, ncost);
				trace[there].push_back(p);
			}
		}
	}

}

int main() {
	int u, v, p;

	while (1) {
		for (int i = 0; i < N; i++) {
			adj[i].clear();
			trace[i].clear();
		}
		scanf("%d %d", &N, &M);
		if (N == 0 && M == 0)
			return 0;
		scanf("%d %d", &S, &D);
		while (M--) {
			scanf("%d %d %d", &u, &v, &p);
			Pos t(v, p);
			adj[u].push_back(t);
		}

		//	처음 최단거리를 구한다.	
		dijkstra();

		//	최단 거리로 가는 간선들을 지워준다.
		queue<int> q;
		q.push(D);
		while (!q.empty()) {
			int here = q.front();
			q.pop();
			
			for (int i = 0; i < trace[here].size(); i++) {
				int there = trace[here][i].v;

				for (int j = 0; j < adj[there].size(); j++) {
					if (adj[there][j].v == here) {
						adj[there][j].p = -1;
						q.push(there);
					}
				}
			}
		}
		//	다시 최단거리를 구한다.
		dijkstra();

		if (dist[D] == 499000)
			printf("-1\n");
		else
			printf("%d\n", dist[D]);

	}

	return 0;
}

skynet0149 5년 전 0

제가 초기에 dist배열을 초기화 시켜줄때 시작점을 0으로 초기화 시켜주어야 했는데 그 부분을 빼먹었었습니다.

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

문제

문제

출처

ICPC

메모리초과가 발생합니다.

skynet0149 5년 전 0

skynet0149 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말