글 읽기 - 메모리 초과가 나옵니다. 어떤부분이 문제일까요?

isvara 3년 전 0

메모리 초과가 큐부분에서 발생은 하는거같은데 어떤상황에서 발생되는지

감이 안잡히내요 혹시 설명해주실 고수분 계실까요?

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>
#include <string.h>
#include<bitset>
#include<set>
#include<functional>
#define debug cout
typedef long long ll;
using namespace std;

const int INF = 2000001;
const int max_n = 100001;
int N, M;
int A, B, C;

vector<pair<int, int>>adj[max_n];
int mini[max_n];
void solve() {
	for (int i = 0; i < N; i++) 
		mini[i] = INF;
	

	priority_queue<pair<int, pair<int, int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>pq;//작은값부터 우선적으로
	pq.push({ 0,{0,A} });//shame,tot,cur
	mini[A] = 0;

	while (!pq.empty()) {
		int shame = pq.top().first;
		int tot = pq.top().second.first;
		int cur = pq.top().second.second;
		pq.pop();

		if (shame > mini[cur])continue;
		if (cur == B)continue;

		for (int i = 0; i < adj[cur].size(); i++) {
			int nxt = adj[cur][i].first;
			int weight = adj[cur][i].second;
			
			if (tot + weight > C)continue;
			
			if (mini[nxt] < max(shame, weight))continue;
			mini[nxt] = max(shame, weight);
			pq.push({ mini[nxt], {tot + weight,nxt} });
		}
	}
	if (mini[B] == INF)cout << -1;
	else cout << mini[B];
}
void input() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	cin >> A >> B >> C;
	A--, B--;
	for (int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		
		u--, v--;

		adj[u].push_back({ v,w });
		adj[v].push_back({ u,w });
	}
}
int main()
{
	input();
	solve();
}

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

문제

문제

출처

ICPC

메모리 초과가 나옵니다. 어떤부분이 문제일까요?

isvara 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말