글 읽기 - 50% 에서 메모리 초과발생

jhh0712 4년 전 0

제 예상으로는 que에 집어넣는 것 때문에 나는 것 같은데

어떤 케이스에서 해당 부분에서 메모리 초과가 나는지 생각이 잘안됩니다.

후.. 도움 주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<pair<int, int>> computer[10001];
int main() {
	
	int T;
	cin >> T;

	for(int i = 0; i < T; i++){
		
		int n, d, c;
		cin >> n >> d >> c;
		
		vector<int> distance;
		
		for(int j = 0; j <= n; j++){
			computer[j].clear();
		}
		
		for(int j = 0; j < d; j++){
			int a, b, s;
			cin >> a >> b >> s;
			computer[b].push_back(make_pair(s, a));
		}
		
		distance.assign(n+1, -1);
		priority_queue<pair<int, int>> que;
		que.push(make_pair(0, c));
		distance[c] = 0;
		
		while(!que.empty()){
			auto node = que.top();
			que.pop();
			
			int cost = node.first;
			int com = node.second;
			
			for(int i = 0; i < computer[com].size(); i++){
				int c = computer[com][i].first;
				int p = computer[com][i].second;
				
				if(distance[p] < -(cost - c) && distance[p] != -1){
					continue;
				}
				que.push(make_pair(cost - c, p));
				distance[p] = -(cost-c);
			}
		}
		
		int result = 0;
		int count = 0;
		for(int i = 1; i <= n; i++){
			if(distance[i] != -1){
				count++;
			}
			result = max(result, distance[i]);
		}
		
		cout << count << " " << result << endl;
	}
	
	return 0;
}

qazyj 2년 전 1

혹시나 이런 분들이 있을 것 같아서 댓글 달아둘게요!

s는 0이 될 수 있있습니다.

만약, d번의 입력중 a,b,s가 1,2,0과 2,1,0의 입력이 있고 그래프를 돌며 distance[1] = 3, distance[2] = 3 처럼 같은 값으로 초기화 되어진 경우 우선순위큐에 무한 번 추가하게되어 메모리초과가 발생할 수 있습니다..!

저처럼 삽질하지 마시길..

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

문제

문제

출처

ICPC

50% 에서 메모리 초과발생

jhh0712 4년 전 0

qazyj 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말