글 읽기 - 5719 메모리초과 도대체 뭐가 문제일까요

uuyzpil 3년 전 0

다익스트라 한번돌리고 최단거리 지우는 remove 에서 메모리초과가 나는것 같은데

도대체 어디가 문제인지 이유를 못찾겄네요

도와주세요ㅠ

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>

using namespace std;

struct Edge
{
	int v;
	long long e;
	bool operator<(const Edge& a)const {
		return e > a.e;
	}
};



int n, m;
int s, d;
vector<Edge> v[501];
vector<Edge> trace[501];
long long cost[501];
bool visited[501][501];

void dik() {
	priority_queue<Edge> q;
	q.push({s,0});
	cost[s] = 0;


	while(!q.empty())
	{ 
		Edge cur = q.top();
		q.pop();

		for (int i = 0; i < v[cur.v].size(); i++)
		{
			Edge next = v[cur.v][i];

			if (next.e == -1) continue;

			if (cost[next.v] > cur.e + next.e)
			{
				q.push({next.v, cur.e + next.e});
				cost[next.v] = cur.e + next.e;
				trace[next.v].clear();
				trace[next.v].push_back({ cur.v, cur.e + next.e });
			}
			else if (cost[next.v] == cur.e + next.e)
			{
				trace[next.v].push_back({ cur.v,cur.e + next.e });
			}		
		}
	}
}

void remove()
{
	queue<int> q;

	q.push(d);
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		for (int i = 0;i<trace[cur].size(); i++)
		{
			int next = trace[cur][i].v;

			if (visited[cur][next] == true ) continue;
			visited[cur][next] == true;
			for (int j = 0; j < v[next].size(); j++)
			{
				if (v[next][j].v == cur)
				{
					v[next][j].e = -1;
				}
			}
			q.push(next);

		}
	}
}
int main(void)
{
	freopen("input.txt", "r", stdin);
	while (true)
	{
		scanf("%d %d", &n, &m);
		if (n == 0 && m == 0) break;
		scanf("%d %d", &s, &d);
		for(int i=0; i<501; i++)
		{
			v[i].clear();
			trace[i].clear();
			cost[i] = LLONG_MAX;
			for (int j = 0; j < 501; j++)
			{
				visited[i][j] = false;
			}
		}

		for (int i = 0; i < m; i++)
		{
			int a, b;
			long long s;
			scanf("%d %d %lld", &a, &b, &s);
			v[a].push_back({ b,s });
		}
		dik();
		remove();
		fill_n(cost, 501, LLONG_MAX);
		dik();
		printf("%d\n", cost[d]);


	}
	return 0;
}

asdsa2134 3년 전 0

경로 지울 때 dfs로 시도해보시면 메모리초과 안날거예요

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

문제

문제

출처

ICPC

5719 메모리초과 도대체 뭐가 문제일까요

uuyzpil 3년 전 0

asdsa2134 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말