글 읽기 - 메모리 초과?

pos10022 6년 전 0

이거 왜 메모리 초과가 나오나요?

bfs로 했습니다.

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

using namespace std;

queue<int> q;
int k,n,r;
int dist[105][105],won[105][105];
int res[105][2],from[105],map[105][105];

int main()
{
	int s,d,l,t,i,j;

	scanf("%d",&k);
	scanf("%d",&n);
	scanf("%d",&r);
	for(i=1;i<=r;i++) {
		scanf("%d %d %d %d",&s,&d,&l,&t);
		map[s][d]=1; from[d]++; dist[s][d]=l; won[s][d]=t;
	}
	for(i=1;i<=n;i++) res[i][0]=res[i][1]=-1;
	res[1][0]=res[1][1]=0;
	q.push(1);
	while(!q.empty()) {
		int cur=q.front();
		q.pop();
		for(i=1;i<=n;i++) {
			if(map[cur][i]==1) {
				from[i]--;
				if((res[i][0]==-1 && res[i][1]==-1) || res[i][1]>res[cur][1]+won[cur][i] || 
					res[cur][1]+won[cur][i]<=k || res[i][0]>res[cur][0]+dist[cur][i]) {
					res[i][0]=res[cur][0]+dist[cur][i];
					res[i][1]=res[cur][1]+won[cur][i];
					q.push(i);
				}
			}
		}
	}
	printf("%d\n",res[n][0]);
}

chogahui05 6년 전 0

뭐가 뭔지는 모르겠지만 어렵지요.

힌트 하나 드릴게요.

min_cost[cost][lloc] = d

cost만큼의 비용을 들여서, 시작점부터 lloc까지 갔을 때 최단 거리 = d 라고 하고 풀어보세요.

방문한 곳을 또 방문하고 또 방문하고 해서 터지는 거 같습니다.

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

문제

문제

출처

ICPC

메모리 초과?

pos10022 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말