글 읽기 - 메모리 초과 관련 질문입니다

jjwdi0 7년 전 0

문제를 요약하자면

'도시 1에서 도시 N으로 가는 데 비용 K 내에서 갈 수 있는 최소 거리를 구하여라'

입니다.

그래서 제가 이렇게 코드를 제출했는데 메모리 초과가 뜹니다.

제 예상에는 std::queue에서 발생하는것 같은데

정확한 이유를 알려주실 분 없나요?ㅠㅠ

참고로 테스트케이스는 모두 정답이 나옵니다.(아마도요)

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 987654321
using namespace std;
struct data{
	int pos, dist, cost;
};
int k, n, r, i, j, ans=INF, dp[103][10003];
pair<pair<int, int>, pair<int, int> >road; // 길의 정보를 담는 변수
queue<data> q; // BFS를 위한 구조체
vector<data> v[103]; // Adjacent List 구현을 위한 std::vector
main()
{
	scanf("%d %d %d", &k, &n, &r);
	for(i=0; i<r; i++)
	{
		scanf("%d %d %d %d", &road.first.first, &road.first.second, &road.second.first, &road.second.second);
		v[road.first.first].push_back({road.first.second, road.second.first, road.second.second});
	}
	q.push({1, 0, 0});
	while(!q.empty())
	{
		data temp=q.front();q.pop(); // queue의 맨 앞 정보를 가져와서 삭제
//		printf("%d %d %d\n", temp.pos, temp.dist, temp.cost); //디버깅 코드
		if(temp.cost>k)continue;
		if(dp[temp.pos][temp.cost] && dp[temp.pos][temp.cost]<=temp.dist)continue;
		dp[temp.pos][temp.cost]=temp.dist;
		for(int j=0; j<v[temp.pos].size(); j++)
		{
			q.push({v[temp.pos][j].pos, v[temp.pos][j].dist+temp.dist, v[temp.pos][j].cost+temp.cost});
		}
	}
	for(i=0; i<=k; i++)
	{
		if(dp[n][i])ans=min(ans, dp[n][i]); // 갈 수 있는지 판별
	}
	printf("%d", min(ans, INF)==INF?-1:ans); // 만약 갈 수 없으면 -1, 있으면 최소값 출력
}

ntopia 7년 전 0

다익스트라를 짜신거면 그냥 queue를 쓸게 아니라 priority_queue 를 쓰셔야 합니다

안그러면 30~33번 줄 때문에 queue에 무한정 들어가요

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

문제

문제

출처

ICPC

메모리 초과 관련 질문입니다

jjwdi0 7년 전 0

ntopia 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말