글 읽기 - 메모리 초과가 납니다

piri007 5년 전 0

최단 경로를 구하는 과정에서 me라는 벡터를 만들어 각 정점마다 어떤 정점으로부터 최단경로가 이어지는지를 저장했습니다.(최단경로가 여러개 나올 수도 있기에 2차원 벡터로 만들었습니다.) 그 후 me벡터를 토대로 간선을 제거합니다.(큐를 이용해 여러개의 최단경로 고려) 다시 한번 최단경로를 구해 거의 최단경로를 출력했습니다. 예제와 질문 속 반례들은 다 맞았으니 답은 맞는거 같은데 메모리 초과가 문제입나다.

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int main()
{
	while (1)
	{
		priority_queue <pair<int, int>> q;
		vector<vector<pair<int, int>>> adj;
		vector<int> mon;
		vector<int> mon2;
		vector<vector<int>> me;


		int n, e, start, finish;
		int u, v, w;

		scanf("%d %d", &n, &e);
		if (n == 0 & e == 0)
			break;
		scanf("%d %d", &start, &finish);
		adj.assign(n + 1, vector<pair<int, int>>());
		for (int i = 0; i < e; i++)
		{
			scanf("%d %d %d", &u, &v, &w);
			adj[u].push_back(make_pair(v, w));
		}
		mon.assign(n + 1, 987654321);
		mon2.assign(n + 1, 987654321);
		me.assign(n + 1, vector<int>());
		mon[start] = 0;
		mon2[start] = 0;

		q.push(make_pair(0, start));
		while (!q.empty())
		{
			int hem = -q.top().first;
			int here = q.top().second;
			q.pop();
			if (mon[here] < hem) continue;

			for (int i = 0; i < adj[here].size(); i++)
			{
				int there = adj[here][i].first;
				int money = adj[here][i].second + hem;

				if (money < mon[there])
				{
					me[there].clear();
					me[there].push_back(here);
					mon[there] = money;
					q.push(make_pair(-money, there));
				}
				else if (money == mon[there])
					me[there].push_back(here);
			}
		}

		queue <int> now;
		now.push(finish);
		while (!now.empty())
		{
			int Now = now.front();
			now.pop();
			for (int k = 0; k < me[Now].size(); k++)
			for (int i = 0; i < adj[me[Now][k]].size(); i++)
			{
				if (adj[me[Now][k]][i].first == Now)
					adj[me[Now][k]].erase(adj[me[Now][k]].begin() + i);

				now.push(me[Now][k]);
			}
		}

		q.push(make_pair(0, start));
		while (!q.empty())
		{
			int hem = -q.top().first;
			int here = q.top().second;
			q.pop();
			if (mon2[here] < hem) continue;

			for (int i = 0; i < adj[here].size(); i++)
			{
				int there = adj[here][i].first;
				int money = adj[here][i].second + hem;

				if (money < mon2[there])
				{
					mon2[there] = money;
					q.push(make_pair(-money, there));
				}
			}
		}

		if (mon2[finish] == 987654321)
			printf("-1\n");
		else
			printf("%d\n", mon2[finish]);
	}
}

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

문제

문제

출처

ICPC

메모리 초과가 납니다

piri007 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말