글 읽기 - 메모리초과 해결하신분 있나요?

(追記) (追記ここまで)

메모리초과 해결하신분 있나요?

1948번 - 임계경로

swrho 2년 전 0

위상정렬을 이용하여 풀었습니다.

아무리 최적화를 해봐도 여기까지가 한계인것 같습니다.

아무리 봐도 메모리 터질만한 부분은 없는데 이상하네요

큐 크기가 계속 넣어서 늘어난 것일까요? 도저히 알 수 가 없네요.

알려주시면 정말 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int MAXN = 1e4 + 5;
const int MAXM = 1e5 + 5;
int N, M, indegree[MAXN], a, b, c, startCity, endCity;
//map<pair<int,int>, int> visit;
bool visit[MAXN] = { false, };
vector<pair<int, int>> adj[MAXN], revAdj[MAXN];
int maxD[MAXN];
struct node {
	int num;
};
queue<node> Q;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("input.txt", "r", stdin);
	cin >> N >> M;
	while (M--) {
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
		revAdj[b].push_back({ a,c });
		indegree[b]++;
	}
	cin >> startCity >> endCity;
	Q.push({ startCity});
	while (!Q.empty()) {
		node cur = Q.front(); Q.pop();
		for (int i = 0; i < adj[cur.num].size(); i++) {
			node newNode = { adj[cur.num][i].first};
			Q.push(newNode);
			maxD[adj[cur.num][i].first] = max(maxD[adj[cur.num][i].first], maxD[cur.num] + adj[cur.num][i].second);
		}
	}
	Q.push({ endCity});
	int bridgeAns = 0;
	while (!Q.empty()) {
		node cur = Q.front(); Q.pop();
		for (int i = 0; i < revAdj[cur.num].size(); i++) {
			if (maxD[cur.num] - revAdj[cur.num][i].second == maxD[revAdj[cur.num][i].first]) {
				node newNode = { revAdj[cur.num][i].first};
				bridgeAns++;
				if (visit[revAdj[cur.num][i].first] == true)
					continue;
				Q.push(newNode);
				visit[revAdj[cur.num][i].first] = true;
			}
		}
	}
	cout << maxD[endCity] << "\n" << bridgeAns;
}

zenith82114 2년 전 0

34줄 while문을 한 번 돌 때마다 큐에서 빠지는 건 1개인데 들어가는 건 adj[cur.num].size() 개니 큐가 안 터지기가 어려울 것 같습니다. 추가로 indegree를 구해놓고 사용하는 곳이 없는 것으로 보아 위상정렬도 제대로 안 되고 있을 걸로 예상합니다.

swrho 2년 전 0

감사합니다 indegree 사용하니깐 맞았습니다 뜨네요.

처음에 indegree를 쓰는 코드를 넣었었는데 계속 바꾸다 보니 지웠네요. 이런 실수 안하도록 해야겠습니다.

감사합니다. 좋은하루되세용

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

메모리초과 해결하신분 있나요?

swrho 2년 전 0

zenith82114 2년 전 0

swrho 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말