글 읽기 - 메모리초과가 왜뜨는걸까요

dtc03012 8년 전 0

priority_queue 부분에서 뜨는 걸까요? 128mb 여서 딱히 뜰만한 곳이 없는거 같은데요..

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

using namespace std;

int map[2222][222],r,c;
int che[2222][222];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

bool checking(int y,int x)
{
	if(0<=x&&x<c&&0<=y&&y<r) return true;
	return false;
}

void dik(int y,int x,int num)
{
	priority_queue<pair<int,pair<int,int> > > q;
	if(num==0)
	{
		q.push({-map[y][x],{y,x}});
		che[y][x]=map[y][x];
	}
	else
	{
		q.push({0,{y,x}});
		che[y][x]=0;
	}
	while(!q.empty())
	{
		int now_x=q.top().second.second;
		int now_y=q.top().second.first;
		int dist=-q.top().first;
		q.pop();
		if(now_x==0||now_x==c-1)
		{
			for(int e=0;e<4;e++)
			{
				if(checking(now_y+dy[e],now_x+dx[e]))
				{
					int wei=dist+map[now_y+dy[e]][now_x+dx[e]];
					if(wei>che[now_y+dy[e]][now_x+dx[e]]) continue;
					else
					{
						che[now_y+dy[e]][now_x+dx[e]]=wei;
						q.push({-wei,{now_y+dy[e],now_x+dx[e]}});
					}
				}
			}
		}
		else
		{
			for(int e=0;e<2;e++)
			{
				if(checking(now_y+dy[e],now_x+dx[e]))
				{
					int wei=dist+map[now_y+dy[e]][now_x+dx[e]];
					if(wei>che[now_y+dy[e]][now_x+dx[e]]) continue;
					else
					{
						che[now_y+dy[e]][now_x+dx[e]]=wei;
						q.push({-wei,{now_y+dy[e],now_x+dx[e]}});
					}
				}
			}
		}
	}
}
int main(void)
{
	int d,tot=0;
	scanf("%d %d",&r,&c);
	for(int e=0;e<r;e++) for(int t=0;t<c;t++) scanf("%d",&map[e][t]);
	scanf("%d",&d);
	int f=0,s=0;
	for(int e=0;e<r;e++) for(int t=0;t<c;t++) che[e][t]=9999999;
	for(int e=0;e<d;e++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		dik(f,s,e);
		tot+=che[a-1][b-1];
		f=a-1;
		s=b-1;
	}
	printf("%d\n",tot);
	return 0;
}

dtc03012 8년 전 0

참고로 vector는 안썼습니다

ntopia 8년 전 0

if(wei>che[now_y+dy[e]][now_x+dx[e]])

이 조건문 말이죠

양변의 값이 같은 경우에서 pq에 해당 항목을 집어넣는데요

그럼 한번 갔던 곳을 또 가는 일이 생겨버려서

결국 메모리초과가 나는 듯 합니다

부등호를 >= 로 바꾸면 잘 될 것 같기도...

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

문제

문제

출처

ICPC

메모리초과가 왜뜨는걸까요

dtc03012 8년 전 0

dtc03012 8년 전 0

ntopia 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말