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

yajunseo313 2년 전 0

배열로 했다가 메모리 초과가 떠서 vector 를 이용해서 구현을 해봤는데요

똑같이 초과가 뜨네요 어떤식으로 수정해야 더 효율적이게 될까요??

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int v, e;
int k;
int ls, le, w;
vector<pair<int, int>> vCourse[20001];

int findShortCourse(int start, int end, int width) 
{
	for (int i = 0; i < vCourse[start].size(); i++)
	{
		if(vCourse[start][i].first == end)
			return width + vCourse[start][i].second;
	}

	int temp = 0;

	for (int i = 0; i < vCourse[start].size(); i++)
	{
		temp += findShortCourse(vCourse[start][i].first, end, width);
	}



	if (temp == 0)
		return 0;
}

int main()
{
	cin >> v >> e;
	cin >> k;
	for (int i = 0; i < e; i++)
	{
		cin >> ls >> le >> w;
		vCourse[ls].push_back(make_pair(le, w));
	}

	for (int i = 1; i <= v; i++)
	{
		if (i == k)
			cout << "0" << endl;

		else {
			int course = findShortCourse(k, i, 0);
			if (course == 0)
				cout << "INF" << endl;
			else
				cout << course << endl;
		}
	}


	return 0;
}

djs100201 2년 전 0

일반적인 그래프 탐색으로 해결할 수 없습니다.
최단경로 알고리즘을 공부해야 합니다.

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

문제

문제

출처

ICPC

메모리 초과 질문입니다.

yajunseo313 2년 전 0

djs100201 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말