글 읽기 - 66퍼에서 메모리 초과가 나네요 ㅠㅠ

aza1200 3년 전 1

가장 일반적으로

다익스트라 의 shortest 배열에 모든 점에 대해서 각각의 최단 경로값을 구해주고 그

과정에서 before [2002] 의 배열에 바로 그직전 해당점을 저장하는 방식으로 문제를 풀었습니다.

그리고

before 라는 배열을 이용해서 bfs 방식으로 마지막에서 내려가는 방식으로 돌면서

그 과정에서 g,h 가 존재할시 답 -> 즉 answer라는 vector 에 집어넣는 방식으로 풀었으나

66퍼에서 메모리 초과가 나네요 이이유 아시는분 계시나요 ㅠㅠㅠ

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int T;

struct load {
	int to;
	int cost;
	int before;
	load(int a, int b) : to(a), cost(b) {};
	load(int a,int b,int c): to(a),cost(b),before(c){}
};

bool operator<(load a, load b) {
	return a.cost > b.cost;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--) {
		int n, m, t,s, g, h;
		cin >> n >> m >> t;
		cin >> s >> g >> h;

		vector<load> vec[2004];
		vector<int> target,before[2003];
		int shortest[2003];

		for (int i = 1; i <= n; i++) shortest[i] = 987654321;

		while (m--) {
			int a, b, d;
			cin >> a >> b >> d;
			vec[a].push_back(load(b, d));
			vec[b].push_back(load(a, d));
		}
		while (t--) {
			int number;
			cin >> number; target.push_back(number);
		}

		priority_queue<load> pq;
		pq.push(load(s, 0,s));

		while (!pq.empty()) {
			load now = pq.top(); pq.pop();
			int to = now.to;
			int dist = now.cost;

			if (shortest[to] < dist) continue;
			shortest[to] = dist;
			before[to].push_back(now.before);
			
			for (int i = 0; i < vec[to].size(); i++) {
				int next_to = vec[to][i].to;
				int next_dist = dist + vec[to][i].cost;
				
				if (shortest[next_to] == 987654321) {
					pq.push(load(next_to, next_dist, to));
				}
			}

	

		}

		vector<int> answer;



		for (int i = 0; i < target.size(); i++) {
			bool check = false;
			int now_end = target[i];

			queue<pair<int, int> > q; q.push({ now_end,now_end });

			while (!q.empty()) {
				int start = q.front().first;
				int end   = q.front().second;
				q.pop();

				if ((start == g && end == h) || (start == h && end == g)) {
					check = true;
					break;
				}

				if (start == s) continue;
				for (int i = 0; i < before[start].size(); i++) {
					q.push({ before[start][i] ,start });
				}

			}

			if (check) answer.push_back(now_end);
		}

		sort(answer.begin(), answer.end());
		for (int i = 0; i < answer.size(); i++) cout << answer[i] << " ";
		cout << '\n';
	}
}

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

문제

문제

출처

ICPC

66퍼에서 메모리 초과가 나네요 ㅠㅠ

aza1200 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말