글 읽기 - 메모리초과

huhbomi 3년 전 0

DFS로 1부터 N까지 가는 경로의 시간을 구했습니다.

마지막 경로에 도착하면 걸린 시간이 가장 큰 K개를 총 걸린시간에서 빼주웠습니다.

도대체 왜 메모리초과가 나온느지 모르겠어요ㅠ

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

struct ROAD {
	int Finish;
	long long Time;
};

int N, M, K;
int S, F;
long long T;
long long ANS = -1;
int visit[10001] = { 0, };
vector<ROAD> Start[10001];

void move(int now, long long time_sum, vector<long long> time_rank) {
	int i, j, next;
	long long t;

	if (now == N) {//목적지 도착
		for (i = 0; i < time_rank.size(); i++) {
			time_sum -= time_rank[i];
		}

		if (ANS == -1) {
			ANS = time_sum;
		}
		else
			ANS = min(ANS, time_sum);

		return;
	}

	for (i = 0; i < Start[now].size(); i++) {
		next = Start[now][i].Finish;
		t = Start[now][i].Time;

		if (visit[next] == 0) {
			visit[next] = 1;

			vector<long long> next_time_rank = time_rank;

			if (next_time_rank.size() < K) {
				next_time_rank.push_back(t);
			}
			else {
				if (t > next_time_rank.back()) {
					next_time_rank.pop_back();
					next_time_rank.push_back(t);
				}
			}
			sort(next_time_rank.begin(), next_time_rank.end(), greater<int>());

			move(next, time_sum + t, next_time_rank);			
			visit[next] = 0;			
		}
	}

	return;
}

bool cmp(ROAD a, ROAD b) {
	if (a.Finish > b.Finish)
		return false;
	return true;
}


int main() {
	int i, j;

	cin >> N >> M >> K;

	//N = 10000, K = 100;
	//for (i = 1; i <= 10000; i++) {
	//	for (j = 1; j <= 10000; j++) {
	//		ROAD r;
	//		r.Finish = j, r.Time = (long long)1000000;
	//		Start[i].push_back(r);
	//	}
	//}


	for (i = 0; i < M; i++) {
		cin >> S >> F >> T;
		
		Start[S].push_back({F,T});
		Start[F].push_back({S,T});
	}

	for (i = 1; i <= N; i++) {
		sort(Start[i].begin(), Start[i].end(), cmp);
	}

	vector<long long> t;
	
	visit[1] = 1;

	if (Start[1].back().Finish == N)
		cout << "0";
	else {
		move(1, (long long)0, t);
		cout << ANS;
	}
}

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

문제

문제

출처

ICPC

메모리초과

huhbomi 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말